mersenneforum.org  

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

Reply
 
Thread Tools
Old 2021-11-25, 17:46   #1
kijinSeija
 
Mar 2021
France

41 Posts
Minus A new Wagstaff PRP test ?

Let Wq=(2^q+1)/3, S0=(2^(q-2)+1)/3, and: Si+1=S2i−2 (mod Wq)

Wq is a prime iff: Sq−1 ≡ S0 (mod Wq)

I used this code on PariDroid (thanks to T.Rex) to check with some prime numbers and it seems it works for 29 and 37 I don't have Sq−1 ≡ S0 (mod Wq)

For exemple q = 29

q=29;Wq=(2^q+1)/3;S0=(2^(q-2)+1)/3;print(q," ",Wq);print(Mod(S0,Wq));S=S0;for(i=1,q-1,S=Mod(S^2-2,Wq);print(S))

This is a viable test or not ?

Thanks :)
kijinSeija is offline   Reply With Quote
Old 2021-11-25, 18:41   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

157710 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
This is a viable test or not ?
Thanks :)
It will become a viable test when you prove that it generates all Wagstaff primes, and gives no composites. Until that it is "only" a claim.
Thanks:)
R. Gerbicz is offline   Reply With Quote
Old 2021-11-26, 05:21   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

7·613 Posts
Default

Quote:
Originally Posted by kijinSeija View Post

q=29;Wq=(2^q+1)/3;S0=(2^(q-2)+1)/3;print(q," ",Wq);print(Mod(S0,Wq));S=S0;for(i=1,q-1,S=Mod(S^2-2,Wq);print(S))

This is a viable test or not ?
This looks promising. Prove it, if you can.

You might write the code as:

Code:
wag(q)=W=(2^q+1)/3;S0=S=Mod((2^(q-2)+1)/3,W);for(i=2,q,S=S^2-2);S==S0;

Last fiddled with by paulunderwood on 2021-11-26 at 08:20
paulunderwood is offline   Reply With Quote
Old 2021-11-26, 13:12   #4
kijinSeija
 
Mar 2021
France

2916 Posts
Default

Thanks for your reply :)

Unfortunately, I'm not a mathematician so I think it could be impossible for me to prove it. I try to understand the proof of the Lucas-Lehmer test and trying to transpose it with Wagstaff primes but I don't understand completly the Lucas-Lehmer test. So trying to find a proof for Wagstaff primes is not possible for me I guess.
kijinSeija is offline   Reply With Quote
Old 2021-11-26, 15:13   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

7×613 Posts
Default

Quote:
Originally Posted by paulunderwood View Post

Code:
wag(q)=W=(2^q+1)/3;S0=S=Mod((2^(q-2)+1)/3,W);for(i=2,q,S=S^2-2);S==S0;
4*S = (2^q+4)/3 == 1 mod W.

So S = 1/4 mod W

Therefore
S0 = 1/4
S1 = (1/4)^2 - 2 = -31/16
S2 = (-31/16)^2 - 2 = 449/256
....
S_{q-1} = X/4^2^(q-1). This will be X if W is 4-PRP -- aren't all Wagstaff numbers? So it remains to show X = 1 mod W iff W is prime.

Last fiddled with by paulunderwood on 2021-11-26 at 15:54
paulunderwood is offline   Reply With Quote
Old 2021-11-26, 20:47   #6
kijinSeija
 
Mar 2021
France

41 Posts
Default

I try some new seeds and I found this :

Let Wq=(2^q+1)/3, S0=q^2, and: S(i+1)=Si² (mod Wq)

Wq is a prime iff: Sq−1 ≡ S0 (mod Wq)

I tried until p<1000 and I found only Wagstaff prime

I used this code on Paridroid :

T(q)={Wq=(2^q+1)/3;S0=q^2;S=S0;print("q= ",q);for(i=1,q-1,S=Mod(S^2,Wq));if(S==S0,print("prime"))}
forprime(n=3,1000,T(n))

I don't know if the "-2" in the iteration part is important becauses it vanishes here but it seems it works with Mersenne numbers Mq=(2^q-1) too

And I tried with Fq=(3^q-1)/2 with S0=q³ and S(i+1)=Si³ and I found this https://oeis.org/A028491 for the prime numbers

Maybe we can extend this for (n^q-1)/(n-1) and (n^q+1)/(n+1) with S0=q^n and S(i+1)=Si^n but I don't know
kijinSeija is offline   Reply With Quote
Old 2021-11-26, 21:04   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

157710 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
Thanks for your reply :)

Unfortunately, I'm not a mathematician so I think it could be impossible for me to prove it. I try to understand the proof of the Lucas-Lehmer test and trying to transpose it with Wagstaff primes but I don't understand completly the Lucas-Lehmer test. So trying to find a proof for Wagstaff primes is not possible for me I guess.
Wagstaff numbers are pretty special cyclotomic numbers, these are polcyclo(2*p,2)=(2^p+1)/3.
There is no known fast tests (at speed of LL test), though there could be! Note that here for example polcyclo(p,2)=2^p-1 and we have the LL test for these.

This is a same/similar problem to find a test for repunits, (10^p-1)/9 because those are polcyclo(p,10).
R. Gerbicz is offline   Reply With Quote
Old 2021-11-27, 13:43   #8
kijinSeija
 
Mar 2021
France

4110 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Wagstaff numbers are pretty special cyclotomic numbers, these are polcyclo(2*p,2)=(2^p+1)/3.
There is no known fast tests (at speed of LL test), though there could be! Note that here for example polcyclo(p,2)=2^p-1 and we have the LL test for these.

This is a same/similar problem to find a test for repunits, (10^p-1)/9 because those are polcyclo(p,10).
For the repunits test. I use T(q)={Wq=(10^q-1)/9;S0=q^10;S=S0;print("q= ",q);for(i=1,q-1,S=Mod(S^10,Wq));if(S==S0,print("prime"))}
forprime(n=3,1050,T(n)) on Pari Gp and I found for q prime : 3, 19, 23, 317, 1031,

3 is obviously wrong but the other prime seems to be ok.

I think this test works for (n^p-1)/(n-1) when p>n (to eliminate 3 for example) but of course this is just an intuition.
kijinSeija is offline   Reply With Quote
Old 2022-02-08, 15:23   #9
JCoveiro
 
"Jorge Coveiro"
Nov 2006
Moura, Portugal

24·3 Posts
Thumbs up fix

For Mersenne:

t1(q)={w=(2^q-1);S0=4;S=S0;for(i=1,q-1,S=Mod(S^2-2,w));s1=lift(Mod(S-5-9,w));s2=lift(Mod(S-5+9,w));if(s2==2,print1(q","))}
forprime(x=3,5000,t1(x))

Code:
3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,
For Wagstaff:

t2(q)={w=(2^q+1)/3;S0=4;S=S0;for(i=1,q-1,S=Mod(S^2-2,w));s1=lift(Mod(S-5-9,w));s2=lift(Mod(S-5+9,w));if((s1==0)||(s2==0),print1(q","))}
forprime(x=3,5000,t2(x))

Code:
3,5,7,11,13,17,19,23,31,43,61,79,101,127,167,191,199,313,347,701,1709,2617,3539,

Last fiddled with by JCoveiro on 2022-02-08 at 15:24
JCoveiro is offline   Reply With Quote
Old 2022-02-08, 16:04   #10
JCoveiro
 
"Jorge Coveiro"
Nov 2006
Moura, Portugal

24×3 Posts
Default more fixes in wagstaff

t3(q)={w=(2^q+1)/3;s=4;for(i=1,q-1,s=(s^2-2)%(w));s1=lift(Mod(s-5-9,w));s2=lift(Mod(s-5+9,w));if((s1==0)||(s2==0),print1(q","))}
forprime(x=3,5000,t3(x))

Code:
3,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-02-08, 16:08   #11
JCoveiro
 
"Jorge Coveiro"
Nov 2006
Moura, Portugal

4810 Posts
Default what if?

t(q)={w=(2^q+1)/3;s=4;for(i=1,q-1,s=(s^2-2)%(w));s1=lift(Mod(s-5-9,w));s2=lift(Mod(s-5+9,w));if((s1==0)||(s2==0),print1(q","))}
forprime(x=3,5000,t(x))

Code:
3,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
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Another Wagstaff PRP Test paulunderwood Wagstaff PRP Search 10 2022-03-31 04:19
Status of Wagstaff testing? and testing Mersenne primes for Wagstaff-ness GP2 Wagstaff PRP Search 414 2020-12-27 08:11
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 23:47.


Mon Oct 3 23:47:12 UTC 2022 up 46 days, 21:15, 0 users, load averages: 1.41, 1.32, 1.16

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.

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