20180802, 15:28  #67  
"Robert Gerbicz"
Oct 2005
Hungary
1,531 Posts 
Quote:
you should use w=(3*d*(ress))%(2^t) instead of w=(d*(sres))%(2^t); (what used for Mersenne numbers), if p>t=512 (or whatever you use). If we wouldn't want a fixed bitlength residue, then RES_t is a good choice where say t=16*floor(log2(p)), and then you have to redo the prp test only when d>2^t or when my test is showing that N/d could be a (probable) prime. 

20180802, 19:40  #68  
Sep 2003
5×11×47 Posts 
Quote:
You define res = 3^mp mod mp and in the formula for w we can substitute: res_t = res mod 2^t But for either Mersenne PRP=1,2,n,1 or Wagstaff PRP=1,2,n,1,"3" , mprime actually calculates: mp = 2^p ± 1 resx = 3^(mp1) mod mp and prints out: resx_t = resx mod 2^t (t = 64 currently) For instance for 2^523 − 1 it gives hex D749C83A364C1462 and for 2^523 + 1 it gives hex 388104444C578BC6 So (3 * resx) mod mp == res but (3 * resx_t) mod 2^t != res_t When t=512 the difference observed is small, only 0 or 1 or 2, but I think it would affect the calculation. So how can we derive res_t from the available printed value resx_t ? Last fiddled with by GP2 on 20180802 at 19:42 

20180802, 22:30  #69  
"Robert Gerbicz"
Oct 2005
Hungary
1,531 Posts 
Quote:
, and that would block my error check. Fortunately there is a workaround: let N=(2^p+1)/3, if N/d is prime then with Fermat's little theorem: 3^(N/d)==3 mod (N/d), from this 3^(2^p)==3^(3*d1) mod (N/d) and the rest is similar to the Mersenne case: (the special case, when b=2: N=(k*2^n+c)/D is similar) Code:
Let N=(2^p+1)/3 res=(3^(2^p) mod (2^p+1)) mod (2^t) s=3^(3*d1) mod (N/d) w=3*d*(ress) mod (2^t) if 3*d<2^t and w>=3*d then N/d is composite, otherwise if 3*d>2^t then we know nothing (too large divisor!) or 3*d<2^t and w<3*d, then N/d can be prime (we are weaker than any Fermat test, because of the "shrinked" residue) Code:
prp(n)=return(Mod(3,n)^n==Mod(3,n)) prpc(maxp)={t=512;num_large_d=0;c0=c1=0;forprime(p=t,maxp, d=1;N=(2^p+1)/3;forstep(q=2*p+1,10000*p,2*p,if(isprime(q)&&lift(Mod(2,q)^p+1)==0,d*=q)); if(d>1&&d<N,res=lift((Mod(3,2^p+1)^(2^p)))%(2^t);s=lift(Mod(3,N/d)^(3*d1)); w=(3*d*(ress))%(2^t); if(3*d>2^t,num_large_d+=1); if(3*d<2^t&&w>=3*d,c0++); if(3*d<2^t&&w<3*d,c1++); if(prp(N/d),print(["Found prp ",p,d])); if(w<3*d&&2^t>3*d,print(["Candidate! ",p,d])))); print("Number of large divisors=",num_large_d); print(c0);print(c1)} prpc(10000) 

20180803, 02:58  #70 
Jun 2003
12233_{8} Posts 
There is a possibility, however remote, of a hidden FFT bug that could miss a prime. For mersennes, we have doublecheck with different rotation, that can detect the issue even if there is FFT bug. But I don't believe Wagstaff numbers can do the bit rotation trick (corrections welcome!). So your confidence in the integrity of the result is predicated upon your confidence about the software.
Having said that, a single pass with GEC PRP should be sufficient to rule out such issues. 
20180803, 03:45  #71 
Sep 2003
101000011001_{2} Posts 
I wrote some Python code for the Gerbicz quicktest method which determines in many cases that a PRP cofactor is composite without actually doing a PRP cofactor test.
I find Python a little more comfortable to use than PARI/GP. The code is attached (gerbicz_quickprp.tar.gz) Last fiddled with by GP2 on 20180803 at 04:03 
20180803, 12:01  #72  
"Robert Gerbicz"
Oct 2005
Hungary
2773_{8} Posts 
Quote:
Looks like good, have you checked that this finds all "known" (probable) primes for Mersenne/Wagstaff case in your range? (ofcourse not including the numbers where Mp,W(p) is prime). My super light sieve only finds prp numbers at p=557,1171,1627,3329 for Wagstaff case in that p=512..5000 range. 

20180803, 14:11  #73  
Sep 2003
5·11·47 Posts 
Quote:
Code:
{"status":"C", "exponent":78358739, "worktype":"PRP3", "res64":"EF71CC587195371C", "residuetype":1, "fftlength":4587520, "shiftcount":75805076, "errorcode":"00000000", ... Code:
{"status":"C", "exponent":6444727, "knownfactors":"373794167,176482404169", "worktype":"PRP3", "res64":"B3948091270BC85C", "residuetype":5, "fftlength":327680, "shiftcount":3602762, "errorcode":"00000000", ... Code:
{"status":"C", "k":1, "b":2, "n":31873, "c":1, "knownfactors":"3", "worktype":"PRP3", "res64":"130344E20CCBF5EE", "residuetype":5, "fftlength":1536, "errorcode":"00000000", ... Quote:
In the code I posted, the slowest step by far is the line where I calculate the 512bit residue myself in Python, rather than getting it from a future version of mprime that will hopefully have the capability of displaying largebitsize residues. Code:
res = pow(a, mp  1, mp) % pow2_t Code:
from gmpy2 import mpz mpz_a = mpz(a) ... ... res = pow(mpz_a, mp  1, mp) % pow2_t Last fiddled with by GP2 on 20180803 at 14:14 

20180803, 17:48  #74  
"Robert Gerbicz"
Oct 2005
Hungary
1,531 Posts 
Quote:
if you start with base=3*2^shift, where 0<=shift<2*p (but it is right to restrict to 0<=shift<p). then the final residue is: res=(3*2^shift)^(2^p)==3^(2^p)*2^(2*shift) mod (2^p+1) so to get the original final (nonshifted) residue: res'=res*2^(2*p2*shift) mod (2^p+1). 

20180804, 00:51  #75 
Sep 2003
5×11×47 Posts 
I tested up to p = 50k for both Mersenne and Wagstaff.
With 2048bit residues there are no false positives, and obviously no false negatives. Updated programs and datafiles with largebitsize residues are attached. 
20180804, 02:16  #76  
Jun 2003
1010010011011_{2} Posts 
Quote:
HOWEVER, what is the math for recovering intermediate residues? Because there is an interest in getting intermediate residues at specific milestone as well. Anyway, if we're using GEC, then the shift trick is superfluous. It doesn't bring any extra safety to the project. It is merely a nicetohave. Last fiddled with by axn on 20180804 at 02:16 Reason: correctly > currently 

20180804, 10:32  #77  
"Robert Gerbicz"
Oct 2005
Hungary
1,531 Posts 
Quote:
Quote:
Correct. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Testing Mersenne Primes with Elliptic Curves  a nicol  Math  3  20171115 20:23 
New Wagstaff PRP exponents  ryanp  Wagstaff PRP Search  26  20131018 01:33 
Hot tuna!  a p75 and a p79 by Sam Wagstaff!  Batalov  GMPECM  9  20120824 10:26 
Statistical odds for prime in Wagstaff vs Mersenne  diep  Math  27  20100113 20:18 
Speed of P1 testing vs. Trial Factoring testing  eepiccolo  Math  6  20060328 20:53 