## Re: sufficent test for prime mod 4 = 3 ?

Expand Messages
• ... This looks to be hard to fool, since it is very similar to BPSW. However it is wilful nonsense to claim that such a test proves primality. Please replace
Message 1 of 4 , Oct 24, 2010
"bhelmes_1" <bhelmes@...> wrote:

> let be b the smallest non quadric residium.
> Necessary: b^((p-1)/2)=p-1 mod p
> Sufficent: (b+I)^p = b^p + I^p = b - I

This looks to be hard to fool, since it is very similar to BPSW.
However it is wilful nonsense to claim that such a test
proves primality. Please replace "suffic[i]ent" by "necessary".

David
• ... It s very easy to fool your test, in that case: {tst(n,b)=n%4==3&&kronecker(b,n)==-1&& Mod(b,n)^((n-1)/2)==-1&& Mod(Mod(1,n)*(b+x),x^2+1)^n==b-x;}
Message 2 of 4 , Oct 24, 2010
"bhelmes_1" <bhelmes@...> wrote:

> there might be counterexamples if you do not take the smallest b

It's very easy to fool your test, in that case:

{tst(n,b)=n%4==3&&kronecker(b,n)==-1&&
Mod(b,n)^((n-1)/2)==-1&&
Mod(Mod(1,n)*(b+x),x^2+1)^n==b-x;}

if(tst(337*3079,298117),print(fooled));

fooled

David
• ... Wrong again. You are still using 1+3=4 selfridges. Please see Theorem 3.5.8 of Crandall and Pomerance. David
Message 3 of 4 , Oct 24, 2010