20180507, 20:21  #1 
Sep 2002
Database er0rr
2^{2}×1,063 Posts 
Another Wagstaff PRP Test
Here are tests for Wagstaff (2^p+1)/3:
If p==1 mod 6: Code:
w1(p)=s=Mod(4,(2^p+1)/3);for(k=1,p2,s=s^22);s==4 Code:
w5(p)=s=Mod(4,(2^p+1)/3);for(k=1,p1,s=s^22);s==4 
20180510, 14:31  #2  
Feb 2017
Nowhere
2^{2}·7·211 Posts 
Quote:
Let u = Mod(x, x^2  4*x + 1), so that u^2  4*u + 1 = 0. Let R = Z[u] = ring of algebraic integers in Q(sqrt(3)). If p == 5 (mod 6), then M == 2 (mod 3). If M is prime, then (3/M) = +1, so MR = PP', R/P and R/P' both isomorphic to Z/MZ. Thus u^(M1) == 1 (mod MR). If v = u  1, we have norm(v) = 2, so that v^(M1) == 1 (mod MR) also. Now v^2 = 2*u, so that v^(M1) = 2^((M1)/2) * u^((M1)/2). Thus 2^((M1)/2) * u^((M1)/2) == 1 (mod MR). Now (2/M) = 1, so we have u^((M1)/2) == 1 (mod MR). Cubing, we obtain u^(2^(p1)  1) == 1 (mod MR), or u^(2^(p1)) == u (mod MR), which validates Paul's test as a necessary condition that (2^p + 1)/3 be prime, when p == 5 (mod 6).  If p == 1 (mod 6), then M == 1 (mod 3). If M is prime, then (3/M) = 1, so MR is a prime ideal, and R/MR = GF(M^2). In this case, the Frobenius automorphism gives us that, for any r in R, if r' is the algebraic conjugate of r, r^M == r' (mod MR), so that r^(M+1) == r*r' = norm(r) (mod M). In particular, u^(M+1) == 1 (mod MR) and v^(M+1) == 2 (mod MR). Proceeding as above, we obtain 2 == 2^((M+1)/2) * u^((M+1)/2). Now 2^((M+1)/2) = 2*(2^((M1)/2) == 2 (mod M), since (2/M) = 1. Therefore u^((M+1)/2) == +1 (mod MR). This tells us that u^((M+1)/4) == +1 or 1 (mod MR). If +1 is correct, we obtain u^(2^(p2)) == u^(1) (mod MR), which would validate Paul's test as a necessary condition that (2^p + 1)/3 be prime, when p == 1 (mod 6). Alas, I have so far been unable to determine in general whether it is +1 or 1. I note that in this case, M == 19 (mod 24). I looked at u^((q+1)/4) (mod qR) for q prime, q == 19 (mod 24) and found that u^((q+1)/4) == +1 (mod qR) about half the time, and u^((q+1)/4) == 1 (mod qR) about half the time. The smallest q == 19 (mod 24) for which u^((q+1)/4) == 1 (mod qR) is q = 67. And that's as far as I've gotten. 

20180513, 12:38  #3  
Feb 2017
Nowhere
5908_{10} Posts 
Quote:
I'm not sure whether this was just a typo, or an instance of minus signs being one of the banes of my existence :( I used the correct value norm(v) = 2 in the other, asyetunfinished case p == 1 (mod 6). 

20180513, 13:37  #4 
Aug 2006
5,981 Posts 

20200725, 15:49  #5 
Sep 2002
Database er0rr
1000010011100_{2} Posts 
Consider x^22*x1=0. This has solutions x= 1 + sqrt(2). But 2^((W1)/2) == 1 mod W where W=(2^p+1)/3 because kronecker(2,W) == 1. I propose the test:
Mod(Mod(1,W)*x,x^22*x1)^(W+1)==1 for Wagstaffs. Last fiddled with by paulunderwood on 20200725 at 15:54 
20200818, 18:18  #6  
Feb 2004
France
929 Posts 
Quote:
Found by means of (Pari/gp): L = [5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539] T(x)={for(i=1,length(L),q=L[i];m=q%6;W=(2^q+1)/3;y=Mod(x,W); if(m==1,J=q2;S=lift(y),J=q1;S=Wlift(y)); if(q==29q==37,v=0,v=1); S0=Mod(y,W);s=S0;for(j=1,J,s=s^22); F=0;if(lift(S)==s,if(v==0,F=1),if(v==1,F=1));if(F==1,break)); if(F==0,print(x," OK"))} for(i=2,30000000,T(i)) 4 OK 52 OK 724 OK 10084 OK 140452 OK 1956244 OK 27246964 OK And we have: 52 = 14*4 4 724 = 14*52 4 10084 = 14*724 52 140452 = 14*10084 724 1956244 = 14*140452 10084 27246964 = 14*1956244 140452 379501252 5285770564 ... which can be easily built by: a=4;b=4;for(i=3,20,a=14*ba;print(a);b=14*ab;print(b)) 52 724 10084 140452 1956244 27246964 379501252 5285770564 73621286644 1025412242452 ........... Does it help? 

20200818, 20:39  #7 
Feb 2004
France
929 Posts 
Looking at: https://oeis.org/A018844 it appears that Wagstaff and Mersenne numbers share half the same seeds: 4, 52, 724, ... {Each seed n is such that n2=2*(m^2) and n+2=[3or6]*(p^2) where m and p are integers (see OEIS above)}
But they do not share the series starting from 10. A part of these seeds can be generated by the Chebitchev C3(x) = x^33*x : ? x=4;x^33*x %76 = 52 ? x=52;x^33*x %77 = 140452 ? x=724;x^33*x %78 = 379501252 .... C2(x)=x^22 (LLT) Looks like it is nearly the same as for Mersenne numbers. Hummmm Since these values (4, 52, 724, .... 21269209556953516583554114034636483645584976452 ...) are valid seeds for each q and Wq=(2^q+1)/3 for the procedure defined by Paul, they are universal seeds, like 4, 10 and 2/3 are universal seed for the LLT for Mersenne numbers. Correct? 
20200818, 22:15  #8 
Feb 2004
France
929 Posts 
Let's also note that the product of all s:
for i=1 to q2, when p==5 mod 6, equals 1 for i=1 to q1, when p==1 mod 6, equals 1 We have a similar property when using VbraReix, starting at s0=1/4 and q1 steps. L = [5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539] T(x)={for(i=1,length(L),q=L[i];m=q%6;W=(2^q+1)/3;y=Mod(x,W); if(m==1,J=q2;S=lift(y);P=W1,J=q1;S=Wlift(y);P=1); if(q==29q==37,v=0,v=1);S0=Mod(y,W);s=S0;p=Mod(1,W); for(j=1,J,s=s^22;p=p*s); F=0;Fp=0;if(lift(p)!=P,Fp=1); if(lift(s)==S,if(v==0,F=1),if(v==1,F=1));if(F==1,if(Fp==1,break,print("pb ",F," ",Fp," ",p))));if(F==0&&Fp==0,print(x," OK"))} T(1025412242452) 1025412242452 OK 
20220209, 22:26  #9 
"Jorge Coveiro"
Nov 2006
Moura, Portugal
2^{4}·3 Posts 
t3(q)={s=4;for(i=2,q,s=(s^22)%(6*(2^q+1)/3));s=(s14)%(2^(q2)2);if(s==0,print1(q","))}
forprime(x=3,5000,t3(x)) Code:
5,7,11,13,17,19,23,31,43,61,79,101,127,167,191,199,313,347,701,1709,2617,3539, 
20220331, 01:57  #10 
Mar 2022
17 Posts 
Related set of primes
Hello all,
A following is to my knowledge unproven (although I might be ignorant since I’m a recreational type), but also may relate to some of the interest in finding a LucasLehmerlike algorithm for Wagstaff primes that a few people in this forum have described interest in. Consider the numbers (5*4^k + 1)/3, which are the average of two successive numbers of the form (2*4^k+1)/3. Primality of these numbers might be tested using a LucasLehmerlike test – the following appears to work as high as I’ve checked: up to k=1000 have been checked both by standard means as well as the below test, and the results agree for all k except for k=1 (the prime 7, which the below test doesn’t identify as prime). Specifically, setting the LucasLehmer s(0)=4 and using the standard algorithm with s(n)=(s(n)^22) % ((5*4^k + 1)/3), the test indicates primality when s(2k1)^55*s(2k1)^3+5*s(2k1)+4 % ((5*4^k + 1)/3) = 0. As an example: for 6827 (k=6), s(11)=3054. So we compute: (3054^5 5*(3054^3)+5*3054 + 4) % 6827 = 0 which indicates that 6827 is prime. The use of 2k1 steps in the first part of the test, as well as the use of the polynomial x^5x^3+5x were inspired by the paper by H.C. Williams: "A class of primality tests for trinomials which includes the LucasLehmer test" (1982) which developed LucasLehmer tests for numbers of a slightly different form. 
20220331, 04:19  #11 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
5·7·283 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Searching for Wagstaff PRP  T.Rex  Wagstaff PRP Search  191  20210630 17:22 
New Wagstaff PRP exponents  ryanp  Wagstaff PRP Search  26  20131018 01:33 
500€ Reward for a proof for the Wagstaff primality test conjecture  Tony Reix  Wagstaff PRP Search  7  20131010 01:23 
Hot tuna!  a p75 and a p79 by Sam Wagstaff!  Batalov  GMPECM  9  20120824 10:26 
Wagstaff number primality test?  ixfd64  Math  12  20100105 16:36 