- --- In primenumbers@yahoogroups.com,

"bhelmes_1" <bhelmes@...> wrote:

> By the way, is there a mathematical book, about

Indeed there is. Crandall and Pomerance tell you

> complex, adjoined squares and complex adjoined squares number,

> which somebody could recommend ?

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 - --- In primenumbers@yahoogroups.com,

"bhelmes_1" <bhelmes@...> wrote:

> 1. let a jacobi (a, p)=-1

[4] is meaningless, as it stands.

> 2. let a^(p-1)/2 = -1 mod p

> 3. a^6 =/= 1 mod p

> 4. (1+sqrt (a))^p = 1-sqrt (a)

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....

The group of units (Z/nZ)* is /not/ cyclic

> there is a cyclic order ...

> 3....

> there is a cyclic order ...

if n has at least two distinct odd prime fators.

David