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

Re: "wriggly" pseudoprime puzzle

Expand Messages
  • djbroadhurst
    ... Indeed there is. Crandall and Pomerance tell you what you need to know about the strong Frobenius test Mod(c+x,x^2-a)^p = c-x mod p, with kronecker(a,p) =
    Message 1 of 50 , Sep 6, 2010
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "bhelmes_1" <bhelmes@...> wrote:

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

      Indeed there is. Crandall and Pomerance tell you
      what you need to know about the strong Frobenius test
      Mod(c+x,x^2-a)^p = c-x mod p, with kronecker(a,p) = -1.

      You have merely set c = 1 and then added the strong Fermat test
      a^((p-1)/2) = -1 mod p.

      Your choice of c = 1 was a *big* mistake, since the Fermat part of
      the Frobenius test is clearly
      (c^2-a)^(p-1) = 1 mod p.

      C&P carefully explain that the 3 selfridges spent
      by Grantham on a Frobenius test include 1 selfridge
      for the latter Fermat test, as well as 2 selfridges
      for the truly Lucas part of the test. With c = 1, you
      allowed me to use a semiprime p = q*r, with a^6 = 1 mod r.
      Then c^2-a = 1-a is *also* a 6th root, modulo r, and it
      is *very* easy to fool *both* of your Fermat tests :-)

      So the only non-trivial part was to fool a single Lucas test.

      As I have now shown, in careful mathematical detail,
      that amounts to arranging for
      (1+s)^q = 1-s mod r ...... [#]
      where s^2 = a mod r. I chose
      (r-1)/(q^2-1) = 2/3 and found that q = 9411892579 does
      the trick, producing 600 million false witnesses in 2 hours.

      I have many other simple values for (r-1)/(q^2-1)
      that do the same trick. Here are merely 8 examples:

      {bhfool(p,a)=if(kronecker(a,p)==-1&&Mod(a,p)^((p-1)/2)==-1
      &&Mod(Mod(1,p)*(1+x),x^2-a)^p==1-x,
      print("fooled with order "znorder(Mod(a,p))));}

      {ls=[[2211631,1686424],
      [10223590001412515419,10109962454545171],
      [6831186997578211927,290495673872036705],
      [660573030595663320319,1269373044712406074],
      [2597100046523211054619,1339538596693991943],
      [11555217916081193504851,13535981161815094957],
      [3716113428540859640779,3108407254242002052432],
      [20249887502321338588837147,11028328009894439310045592]];
      for(k=1,#ls,w=ls[k];bhfool(w[1],w[2]));}

      fooled with order 30
      fooled with order 18654
      fooled with order 19194
      fooled with order 171462
      fooled with order 240162
      fooled with order 316050
      fooled with order 811182
      fooled with order 31879698

      Hint: All of these false witnesses fail my gremlin trap:
      gcd(a^6-1,p) = 1, yet you wrote, with a smile:

      > Pure chance ;-)

      I disagree with this "Kritik der meinen reinen Vernunft" :-)

      I have given, above, a compellingly pure reason why your
      a^6 = 1 mod r loop-hole watered down the 4 selfridges
      that you spend to merely 2 effective selfridges.
      And then fooling a 2-selfridge Lucas test is fairly
      routine, if you will read Arnault's thesis.

      However finding a single false witness that also passes my
      gremlin trap appears to be very difficult, to me at least.

      David
    • 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, 2011
      • 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.