View Single Post
 2017-08-13, 12:13 #88 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 153110 Posts 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(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.