20180507, 20:21  #1 
Sep 2002
Database er0rr
3^{2}·7·53 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
110100001110_{2} 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
D0E_{16} 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
2×5×587 Posts 

20200725, 15:49  #5 
Sep 2002
Database er0rr
D0B_{16} 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 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Searching for Wagstaff PRP  T.Rex  Wagstaff PRP Search  190  20200713 21:44 
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 