mersenneforum.org Another Wagstaff PRP Test
 Register FAQ Search Today's Posts Mark Forums Read

 2018-05-07, 20:21 #1 paulunderwood     Sep 2002 Database er0rr 32×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,p-2,s=s^2-2);s==4 If p==5 mod 6: Code: w5(p)=s=Mod(4,(2^p+1)/3);for(k=1,p-1,s=s^2-2);s==-4 Can you prove or disprove either of these?
2018-05-10, 14:31   #2
Dr Sardonicus

Feb 2017
Nowhere

2×3×557 Posts

Quote:
 Originally Posted by paulunderwood 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,p-2,s=s^2-2);s==4 If p==5 mod 6: Code: w5(p)=s=Mod(4,(2^p+1)/3);for(k=1,p-1,s=s^2-2);s==-4 Can you prove or disprove either of these?
let p > 3 be a prime number, M = (2^p + 1)/3. Then M == 3 (mod 8).

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^(M-1) == 1 (mod MR).

If v = u - 1, we have norm(v) = 2, so that

v^(M-1) == 1 (mod MR) also. Now

v^2 = 2*u, so that

v^(M-1) = 2^((M-1)/2) * u^((M-1)/2). Thus

2^((M-1)/2) * u^((M-1)/2) == 1 (mod MR). Now (2/M) = -1, so we have

u^((M-1)/2) == -1 (mod MR). Cubing, we obtain

u^(2^(p-1) - 1) == -1 (mod MR), or

u^(2^(p-1)) == -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^((M-1)/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^(p-2)) == 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.

2018-05-13, 12:38   #3
Dr Sardonicus

Feb 2017
Nowhere

2·3·557 Posts

Quote:
 Originally Posted by Dr Sardonicus [snip] If v = u - 1, we have norm(v) = 2, so that v^(M-1) == 1 (mod MR) also. [snip]
Of course, norm(v) = -2, not 2. Luckily, all I needed this for in the case p == 5 (mod 6) was to check that v was relatively prime to M, i.e. vR + MR = R.

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, as-yet-unfinished case p == 1 (mod 6).

2018-05-13, 13:37   #4
CRGreathouse

Aug 2006

3×19×103 Posts

Quote:
 Originally Posted by Dr Sardonicus I'm not sure whether this was just a typo, or an instance of minus signs being one of the banes of my existence :-(
You and every other mathematician. Ugh.

 2020-07-25, 15:49 #5 paulunderwood     Sep 2002 Database er0rr 32·7·53 Posts Consider x^2-2*x-1=0. This has solutions x= 1 +- sqrt(2). But 2^((W-1)/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^2-2*x-1)^(W+1)==-1 for Wagstaffs. Last fiddled with by paulunderwood on 2020-07-25 at 15:54

 Similar Threads Thread Thread Starter Forum Replies Last Post T.Rex Wagstaff PRP Search 190 2020-07-13 21:44 ryanp Wagstaff PRP Search 26 2013-10-18 01:33 Tony Reix Wagstaff PRP Search 7 2013-10-10 01:23 Batalov GMP-ECM 9 2012-08-24 10:26 ixfd64 Math 12 2010-01-05 16:36

All times are UTC. The time now is 14:54.

Thu Aug 13 14:54:08 UTC 2020 up 11:29, 1 user, load averages: 1.83, 1.48, 1.43