Quote:
Originally Posted by paulunderwood
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 .