mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Wagstaff PRP Search

Reply
 
Thread Tools
Old 2018-05-07, 20:21   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·5·421 Posts
Default 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?
paulunderwood is offline   Reply With Quote
Old 2018-05-10, 14:31   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

19×307 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2018-05-13, 12:38   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

19·307 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
[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).
Dr Sardonicus is offline   Reply With Quote
Old 2018-05-13, 13:37   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2020-07-25, 15:49   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

101628 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2020-08-18, 18:18   #6
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16378 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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?
T.Rex is offline   Reply With Quote
Old 2020-08-18, 20:39   #7
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

39F16 Posts
Default

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?
T.Rex is offline   Reply With Quote
Old 2020-08-18, 22:15   #8
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16378 Posts
Default

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
T.Rex is offline   Reply With Quote
Old 2022-02-09, 22:26   #9
JCoveiro
 
"Jorge Coveiro"
Nov 2006
Moura, Portugal

24·3 Posts
Default

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,
JCoveiro is offline   Reply With Quote
Old 2022-03-31, 01:57   #10
pvaldivia
 
Mar 2022

17 Posts
Default 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.
pvaldivia is offline   Reply With Quote
Old 2022-03-31, 04:19   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×19×173 Posts
Default

Quote:
Originally Posted by pvaldivia View Post
I might be ignorant ...
Yet another PRP test.
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Searching for Wagstaff PRP T.Rex Wagstaff PRP Search 191 2021-06-30 17:22
New Wagstaff PRP exponents ryanp Wagstaff PRP Search 26 2013-10-18 01:33
500€ Reward for a proof for the Wagstaff primality test conjecture Tony Reix Wagstaff PRP Search 7 2013-10-10 01:23
Hot tuna! -- a p75 and a p79 by Sam Wagstaff! Batalov GMP-ECM 9 2012-08-24 10:26
Wagstaff number primality test? ixfd64 Math 12 2010-01-05 16:36

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


Sun Jul 3 10:54:00 UTC 2022 up 80 days, 8:55, 0 users, load averages: 1.85, 1.71, 1.68

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔