Loading ...
Sorry, an error occurred while loading the content.

Re: "wriggly" pseudoprime puzzle

Expand Messages
  • bhelmes_1
    Dear David, ... Please give a hint how you produce these impression rate, some mathematical background would be very nice, perhaps also for others. I would
    Message 1 of 50 , Sep 5 1:24 PM
    • 0 Attachment
      Dear David,

      > > 1. p is an odd positive integer
      > > 2. a is an integer with kronecker(a,p) = -1
      > > 3. a^((p-1)/2) = -1 mod p
      > > 5. Mod(1+x,x^2-a)^p = 1-x mod p
      >
      > > Puzzle: Find a pseudoprime, p,
      > > with a false witness, a,
      > > that fools (1), (2), (3), (5) and has
      > > znorder(Mod(a,p)) > 3414.
      >
      > Comment: The gremlins can generate false witnesses
      > for this puzzle at a rate in excess of 50 kHz,
      > finding more than 600,000,000 in less than 3 hours.

      Please give a hint how you produce these impression
      rate, some mathematical background would be very nice,
      perhaps also for others.

      I would like to participate in the calculation,
      but how do you generate pseudoprimes for which (1), (2), (3) and (5)
      are o.k. ?

      By the way, is there a mathematical book, about
      complex, adjoined squares and complex adjoined squares number,
      which somebody could recommand ?

      > Hint: All of these false witnesses fail my gremlin-trap:
      >
      > > 4. gcd(a^6-1,p) = 1

      Pure chance ;-)

      Nice Greetings from the primes
      Bernhard
    • djbroadhurst
      ... [4] is meaningless, as it stands. You should write a double mod: 4. (1+x)^p = 1-x mod(x^2-a,p) ... There is no reason whatsoever to believe that [1] to [4]
      Message 50 of 50 , Sep 29 4:14 AM
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "bhelmes_1" <bhelmes@...> wrote:

        > 1. let a jacobi (a, p)=-1
        > 2. let a^(p-1)/2 = -1 mod p
        > 3. a^6 =/= 1 mod p
        > 4. (1+sqrt (a))^p = 1-sqrt (a)

        [4] is meaningless, as it stands.
        You should write a double mod:

        4. (1+x)^p = 1-x mod(x^2-a,p)

        > 1. Is it possible that there are other exceptions

        There is no reason whatsoever to believe that
        [1] to [4] establish that p is prime. Morevoer,
        some folk believe that, for every epsilon > 0,
        the number of pseudoprimes less than x may
        exceed x^(1-epsilon), for /sufficiently/ large x.

        > 2....
        > there is a cyclic order ...

        > 3....
        > there is a cyclic order ...

        The group of units (Z/nZ)* is /not/ cyclic
        if n has at least two distinct odd prime fators.

        David
      Your message has been successfully submitted and would be delivered to recipients shortly.