## Re: "wriggly" pseudoprime puzzle

Expand Messages
• ... 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
"bhelmes_1" <bhelmes@...> wrote:

> By the way, is there a mathematical book, about
> 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
• ... [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
"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.