20170811, 16:26  #1 
"Robert Gerbicz"
Oct 2005
Hungary
7×229 Posts 
Fast and robust error checking on Proth/Pepin tests
In the recent days an interesting new error checking for LL test appeared, using Jacobi test.
I'll give another type of checking, that detects much more errors (we see later what this means), but works on Proth numbers. The conditions: we allow at most O(log(N)) more memory to solve this, and at most eps overhead in running time (say eps~1/1000 or even smaller). We are seeking a high performance error checking algorithm. Code:
quick background:: N=k*2^n+1 is Proth number if k<2^n, the base=a proves the primality of N, if a^((N1/2)==1 mod N. In special case k=1 for Fermat number, and in this case we can choose a=3 (Pepin). (if we choose a=quadratic nonresidue modulo N, then a^((N1)/2)!=1 mod N proves that N is composite). Code:
Let L=2000 constant (could even depend on n), and L2=L^2. u(t)=(a^k)^(2^t) mod N [0] d(t)=u(0)*u(L)*u(2*L)*...*u(t*L) mod N [1] with this d(t+1)=d(t)*u((t+1)*L) mod N [2] but d(t+1)=u(0)*d(t)^(2^L) mod N [3] is also true. We store only the last term of the d sequence to use identity [2]. (when we compute the next term, then two terms are available, after a possible check we can delete the last but one term). and store u(0)=a^k mod N, the last d[z],u[z], where z is divisible by L2. At each Lth term of the d sequence we check the identity of [3], if this does not hold, then we roll back, notice that it is also possible a computation error of the d sequence, so if we would roll back too much (say 100 times to the same term) then we just restart completely the computation. At the last few squarings in u, we also force an error checking computation of [3] (in that i when i is divisible by L and i+L>=n, this means only one extra checking of [3].) This leaves all potential erros in the (at most) last L squarings in u, or very unlikely errors earlier in u or d. The overhead is n/L mulmods in [2] and n/L2*L=n/L squaremod in [3] and n/L2 mulmods in [3]. so over the n1 mulmods of the Proth test there is approx. n/1000 mulmods, if we count in mulmods everything. So the overhead is 0.1% in time. And we see why we haven't checked all terms of d, we could do that, but in that case the overhead in the error checking would be n/L*(L+1)>n mulmods, and that is a lot, slightly more time what we spend on the Proth test squarings. using PARIGP: 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 N=k*2^n+1 Proth number, we use L at error checking, making errors in the ith 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) we use base=a, this is optional, if you don't give, we find one suitable, (here a=quadratic nonresidue) if printmsg!=0, then we print out some additional info, the return value is (1+a^((N1)/2) mod N), note that for prime the return value is zero. [not forget the 1+ in the formula] If you would not give a Proth number or errpos's length is too small, then the return value is (1). fncheck(N,n,L,errpos,a=0,printmsg=1)={ k=(N1)/(2^n); if(k>=2^nk<1type(k)!="t_INT",if(printmsg,print("Not a Proth number"));return(1)); if(length(errpos)<n1,if(printmsg,print("The errpos array's length should be at least n1"));return(1)); if(a==0,a=2;while(kronecker(a,N)==1,a+=1)); numerr=0; L2=L^2; u0=Mod(a,N)^k; prev_d=u0; saved_u=u0; saved_d=u0; saved_i=0; i=0;res=u0;while(i<n1,i+=1; res=res^2; if(errpos[i]&&random(2),res=myrand(res,N)); if(i%L==0,d=prev_d*res;set_d=0; if(i%L2==0(i%L==0&&i+L>=n), 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))); res+=1; if(printmsg,if(lift(res)==0,print("N is prime."),print("N is composite.")); print("Number of errors (corrected and) detected=",numerr)); return(lift(res))} in each L*L squarings block: suppose that the first L*z squarings was good, and after that in one of the next L squarings there was an error, we got r0!=u0^(e^(z+1)) mod N. (for shortening here we write e=2^L) prev_d=u0*u0^e*u0^(e^2)*u0^(e^3)*...*u0^(e^z)*r0*r0^e*...*r0^(e^w) d =u0*u0^e*u0^(e^2)*u0^(e^3)*...*u0^(e^z)*r0*r0^e*...*r0^(e^w)*r0^(e^(w+1)) d/prev_d^e/u0=r0/u0^(e^(z+1))!=1 mod N, so d!=u0*prev_d^e mod N, so it will be detected. What about multiple errors in the same block, say we've chosen N=13*2^82+1 Proth number and we make errors at i=11,13,43 (at each position with 50% chance), used L=3, this means that i=11,13 are in the same L2=9 length block, so with 25% chance we have double errors. Make the test for 50 times: Code:
N=13*2^82+1;n=82; errpos=vector(n1,i,0);errpos[11]=1;errpos[13]=1;errpos[43]=1; cnt=0;for(h=1,50,cnt+=(fncheck(N,n,3,errpos,0,1)==0);print()); print("Found prime ",cnt," times."); Code:
Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=7 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=1 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=6 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=9 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=3 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=1 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=10 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=5 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=1 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=2 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=2 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=5 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=2 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=4 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=10 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=7 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=4 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=4 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=3 N is prime. Number of errors (corrected and) detected=0 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=1 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=4 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=2 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=14 N is prime. Number of errors (corrected and) detected=0 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=14 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=2 N is prime. Number of errors (corrected and) detected=0 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=2 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=3 N is prime. Number of errors (corrected and) detected=0 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=2 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=1 N is prime. Number of errors (corrected and) detected=0 N is prime. Number of errors (corrected and) detected=0 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=1 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=10 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=5 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=4 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=4 N is prime. Number of errors (corrected and) detected=0 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=4 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=1 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=5 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 N is prime. Number of errors (corrected and) detected=2 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=3 Found error at iteration=18, roll back to iteration=9 Found error at iteration=18, roll back to iteration=9 Found error at iteration=45, roll back to iteration=36 N is prime. Number of errors (corrected and) detected=3 ? Found prime 50 times. ? we are not that far from the truth, lets repeat it with a much smaller number and with more times to see the true error rate: test N=5*2^13+1 Proth number; 1 million times (takes less than a minute), using L=2. Code:
N=5*2^13+1;n=13; errpos=vector(n1,i,0);errpos[5]=1;errpos[7]=1; sum(h=1,1000000,fncheck(N,n,2,errpos,0,0)==0) %12 = 999947 making (at most) two errors, but in different blocks: Code:
N=5*2^13+1;n=13; errpos=vector(n1,i,0);errpos[7]=1;errpos[10]=1; sum(h=1,1000000,fncheck(N,n,2,errpos,0,0)==0) %14 = 1000000 We can easily generalize this error checking to the computation of a^(k*b^t) mod N (for small k). So we can use not only b=2. 
20170816, 00:15  #2 
Sep 2003
13·199 Posts 
More discussion of this idea and its possible applicability to Mersenne numbers is in the thread from the GPU Computing subforum.

20180831, 11:41  #3  
"Mihai Preda"
Apr 2015
2×3×5×47 Posts 
Quote:
e.g. if the P1 is done with lefttoright binary exponentiation. Last fiddled with by preda on 20180831 at 11:42 

20180831, 18:33  #4  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7109_{10} Posts 
Quote:
See also http://mersenneforum.org/showpost.ph...&postcount=245 and http://mersenneforum.org/showpost.ph...&postcount=252 

20180831, 19:58  #5  
"Robert Gerbicz"
Oct 2005
Hungary
7·229 Posts 
Quote:
Trivial extension and speedup: with EulerFermat theorem a^e==a^(e mod eulerphi(d)) mod N, if gcd(a,N)=1, so if dN is also true then a^e==a^(e mod eulerphi(d)) mod d should be also true, if it doesn't hold then we made an error. Ofcourse here calculation of eulerphi(d) is easy, if you know the prime factorization of d. Another small check: if e is even then (res / N) Jacobi symbol should be 1, where res=a^e mod N. And if you make any multiplication error then you can discover it at any iteration with 50% chance. Not counting these I don't know other checks. With a so general e, there is no such ladder trick, unfortunately. ps. you could also post these to the longer error check's thread. 

20180831, 20:37  #6 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
1101111000101_{2} Posts 
There was also the generic error checking and detection thread http://www.mersenneforum.org/showthread.php?t=23467
and a P1 specific Jacobi check thread http://www.mersenneforum.org/showthread.php?t=23470 
20180831, 20:45  #7  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7,109 Posts 
Quote:
Are you contemplating implementing P1 in OpenCL? If so, that would fill a prominent vacancy in the available software versus algorithm and computing platform grid in part one of the attachment at http://www.mersenneforum.org/showpos...91&postcount=2 

20180831, 20:49  #8  
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
Quote:


20180831, 21:26  #9 
"Mihai Preda"
Apr 2015
582_{16} Posts 
Thank you Robert and @kriesel! I'll think about these ideas. In my setup, I don't have a divisor dN. Also the "up to 50%" of Jacobi seems weak IMO.

20180831, 21:33  #10 
"Mihai Preda"
Apr 2015
582_{16} Posts 

20180831, 22:07  #11 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7,109 Posts 
It is what it is, including better than nothing. Two things can make it better than it first seems.
1) It appears, from a test I wrote and ran, that for the early stage 1 powering computations, before the mod Mp kicks in, induced errors don't matter. I think that means they are equivalent to starting with a different base, which is allowed. 2) For tasks like computing the exponent (or partial computation) to which to raise the base, the Jacobi of the product and the product of the Jacobis of the terms can be computed and compared twice, with different denominators, going from ~50% to ~75% detection. I tried denominators M31 and M61 and confirmed that. That's extensible to 3 or more, with diminishing returns and increasing overhead. Whether the checking overhead is worthwhile depends on the error rate. Making error checking optional and the default might be good. One of the challenges with P1 is it's hard to tell from the results produced whether it's all working correctly. Starting by error checking a new installation is advisable. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Use Pepin's Tests for proving primality of Mersenne numbers ?  T.Rex  Math  12  20160403 22:27 
running single tests fast  dragonbud20  Information & Answers  12  20150926 21:40 
Round Off Checking and Sum (Inputs) Error Checking  Forceman  Software  2  20130130 17:32 
Faster LL tests, less error checking?  Prime95  Software  68  20101231 00:06 
Early doublechecking to determine errorprone machines?  GP2  Data  13  20031115 06:59 