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 3·5·281 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

10110110011002 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

22·1,459 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×1,993 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 421510 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
2020-08-18, 18:18   #6
T.Rex

Feb 2004
France

32×103 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?
This holds also when 4 is replaced by: 52, 724, 10084, 140452, 1956244, or 27246964 .

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=q-2;S=lift(y),J=q-1;S=W-lift(y));
if(q==29||q==37,v=0,v=1);
S0=Mod(y,W);s=S0;for(j=1,J,s=s^2-2);
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*b-a;print(a);b=14*a-b;print(b))
52
724
10084
140452
1956244
27246964
379501252
5285770564
73621286644
1025412242452
...........

Does it help?

 2020-08-18, 20:39 #7 T.Rex     Feb 2004 France 11100111112 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 n-2=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^3-3*x : ? x=4;x^3-3*x %76 = 52 ? x=52;x^3-3*x %77 = 140452 ? x=724;x^3-3*x %78 = 379501252 .... C2(x)=x^2-2 (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?
 2020-08-18, 22:15 #8 T.Rex     Feb 2004 France 32·103 Posts Let's also note that the product of all s: for i=1 to q-2, when p==5 mod 6, equals 1 for i=1 to q-1, when p==1 mod 6, equals -1 We have a similar property when using Vbra-Reix, starting at s0=1/4 and q-1 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=q-2;S=lift(y);P=W-1,J=q-1;S=W-lift(y);P=1); if(q==29||q==37,v=0,v=1);S0=Mod(y,W);s=S0;p=Mod(1,W); for(j=1,J,s=s^2-2;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
 2022-02-09, 22:26 #9 JCoveiro   "Jorge Coveiro" Nov 2006 Moura, Portugal 24·3 Posts t3(q)={s=4;for(i=2,q,s=(s^2-2)%(6*(2^q+1)/3));s=(s-14)%(2^(q-2)-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,
 2022-03-31, 01:57 #10 pvaldivia   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 Lucas-Lehmer-like 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 Lucas-Lehmer-like 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 Lucas-Lehmer s(0)=4 and using the standard algorithm with s(n)=(s(n)^2-2) % ((5*4^k + 1)/3), the test indicates primality when s(2k-1)^5-5*s(2k-1)^3+5*s(2k-1)+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 2k-1 steps in the first part of the test, as well as the use of the polynomial x^5-x^3+5x were inspired by the paper by H.C. Williams: "A class of primality tests for trinomials which includes the Lucas-Lehmer test" (1982) which developed Lucas-Lehmer tests for numbers of a slightly different form.
2022-03-31, 04:19   #11
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·32·137 Posts

Quote:
 Originally Posted by pvaldivia I might be ignorant ...
Yet another PRP test.

 Similar Threads Thread Thread Starter Forum Replies Last Post T.Rex Wagstaff PRP Search 191 2021-06-30 17:22 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 05:05.

Thu Jul 7 05:05:41 UTC 2022 up 84 days, 3:07, 0 users, load averages: 1.56, 1.53, 1.44