View Single Post
Old 2015-09-07, 17:32   #16
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

3·307 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Does it produce fewer pseudoprimes than base-a Fermat PRP tests?
If we use the test as-is: ( if(s==sn && ! isprime(N) ), it produces pseudoprimes, like: 1*2^3+1 or 98*2^79+17 .

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100))) : produces 34 pseudoprimes.

But, if we check that no S(i) is equal to S(sn-1) with i=1...n-2 , there are less.

... z=0; forstep(i=n,3,-1, s=sqr(s)-2; if(s==sn, z=1;break));
s=sqr(s)-2;
if(z==0 && s==sn && ! isprime(N), print("k: ",k," c: ",c," n: ",n)))

? for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100))) : there are only 13.
k: 1 c: 1 n: 3
k: 15 c: 1 n: 3
k: 33 c: 25 n: 79
k: 35 c: 17 n: 83
k: 37 c: 17 n: 92
k: 45 c: 1 n: 3
k: 49 c: 17 n: 80
k: 66 c: 25 n: 78
k: 70 c: 17 n: 82
k: 74 c: 17 n: 91
k: 95 c: 17 n: 77
k: 97 c: 17 n: 48
k: 98 c: 17 n: 79

With c=1, 17, or 25 only, within the limits used for k, c and n.
However, there are others, like: 16*2^121+33 .

Up to now, for c>0, they all seem to appear when c = 1 mod 8 : 1, 17, 25, 33, 41, 73 .

For c<0, it seems to appear only with: c= 5, 29 , like: 8*2^158-29 or 11*2^232-5 .

Last fiddled with by T.Rex on 2015-09-07 at 18:07 Reason: Add note about special values of c and -c that create pseudoprimes.
T.Rex is offline   Reply With Quote