View Single Post
Old 2017-08-13, 12:13   #88
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5EE16 Posts
Default

This reliable error checking idea here http://mersenneforum.org/showthread.php?t=22510
from me is just working for Mersenne numbers also!

Why not do a Fermat pseudoprime test for base=3, but (for p>2) in the
equivalent form of res=3^(2^p) mod mp, where mp=2^p-1.
If it is 9 (or correctly it is 9 mod mp), then mp is a prp prime.
And the totally same error checking trick works, what worked for Proth numbers,
with a 0.1% overhead we could get a solid rock test.

Assuming that we need the same time as for LL test to get res, starting with 3, and doing here
p squaremod (we don't need to subtract 2).
And for those p primes that passed this test we should make a Lucas Lehmer test,
to prove that mp is "really" prime.

For what p primes we need to do a LLT: (quick PARI-Gp test up to p=25000)
Code:
forprime(p=2,25000,q=2^p-1;if(Mod(3,q)^(q+1)==Mod(9,q),print1(p",")))
2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213,19937,21701,23209,
as we can see there was no composite fermat prp (for base=3) up to p=25000, ofcourse there could be some in higher range,
though it is likely that there is not even a single prp for Mersenne numbers.


Slightly modified test code, but the heart of the algorithm is the same as for Proth numbers:
(note that here lift(u0)=3 smallish, we would not need to store it)
Code:
myrand(r,N) returns s randomly from [0,N) for that s!=0 and s!=r (the r,s are in Z_N).

myrand(r,N)={local(tmp);while(1,tmp=random(N);if(tmp!=0&&lift(tmp+r)!=0,return(tmp+r)))}

we test mp=2^p-1 Mersenne number (where p is prime),
we use L at error checking, making errors in the i-th squaring
with 50% chance if errpos[i]!=0 (note that if we return to the same i multiple times,
then we choose the making error independently from the previous choices already done)
if printmsg!=0, then we print out some additional info,
the return value is 3^(mp+1) mod mp, note that for prp prime the return value is 9 (correctly 9 mod mp).
If you would not give a p prime or errpos's length is too small, then the return value is (-1).

prpmersenne(p,L,errpos,printmsg=1)={
if(isprime(p)==0,if(printmsg,print("p is not prime."));return(-1));
if(length(errpos)<p,if(printmsg,print("The errpos array's length should be at least p"));return(-1));
mp=2^p-1;
numerr=0;
L2=L^2;
u0=Mod(3,mp);
prev_d=u0;
saved_u=u0;
saved_d=u0;
saved_i=0;
i=0;res=u0;while(i<p,i+=1;
res=res^2;
if(errpos[i]&&random(2),res=myrand(res,mp));
if(i%L==0,d=prev_d*res;set_d=0;
if(i%L2==0||(i%L==0&&i+L>=p),
if(d!=u0*prev_d^(2^L),
numerr+=1;if(printmsg,print("Found error at iteration=",i,", roll back to iteration=",saved_i));
i=saved_i;res=saved_u;prev_d=saved_d;set_d=1,
saved_i=i;saved_u=res;saved_d=d));
if(!set_d,prev_d=d)));
if(printmsg,print1("m",p);if(res==Mod(9,mp),print(" is prp."),print(" is composite."));
print("Number of errors (corrected and) detected=",numerr));
return(lift(res))}
For p=61, test the mp=2^61-1 fifty times, making errors at the i=21,23,45 with L=4:
(i=21,23 are in the same L2=16 block).
Code:
p=61;errpos=vector(p,i,0);errpos[21]=1;errpos[23]=1;errpos[45]=1;
cnt=0;for(h=1,50,cnt+=(prpmersenne(p,4,errpos,1)==9);print());cnt
the result:
Code:
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=4

m61 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=11

m61 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=5

Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=14

m61 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=8

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
m61 is prp.
Number of errors (corrected and) detected=10

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=5

Found error at iteration=32, roll back to iteration=16
m61 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=2

m61 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=2

m61 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=32, roll back to iteration=16
m61 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=3

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
m61 is prp.
Number of errors (corrected and) detected=3

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=4

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
m61 is prp.
Number of errors (corrected and) detected=4

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
m61 is prp.
Number of errors (corrected and) detected=5

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=9

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=8

Found error at iteration=32, roll back to iteration=16
m61 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
m61 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=3

m61 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
m61 is prp.
Number of errors (corrected and) detected=6

Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=6

Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=9

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
m61 is prp.
Number of errors (corrected and) detected=11

Found error at iteration=32, roll back to iteration=16
m61 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=8

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
m61 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
m61 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=7

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=8

Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=4

m61 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
m61 is prp.
Number of errors (corrected and) detected=4

Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=32, roll back to iteration=16
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
Found error at iteration=48, roll back to iteration=32
m61 is prp.
Number of errors (corrected and) detected=11

%5 = 50
?
Corrected and detected all errors in the 50 test runs.

This test with the much smaller mp=2^17-1 with L=2:
Code:
p=17;errpos=vector(p,i,0);errpos[9]=1;errpos[11]=1;
sum(h=1,10^6,prpmersenne(p,2,errpos,0)==9)
%7 = 999988
So out of a million test, it has not found the error(s) in 12 cases,
that is an error rate of less than 2/mp.

Ofcourse for a true run errpos=vector(p,i,0), (a zero array), it is used above only to insert false residues in the squaring computations. And for largish Mersenne computations use L=2000 (or say L=1000), depending on how much overhead you allow.
R. Gerbicz is offline   Reply With Quote