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

23 Posts
Minus A new Wagstaff primality 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

2×3×11×23 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

2×7×281 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

23 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

2×7×281 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

23 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

101111011102 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

816 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
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Another Wagstaff PRP Test paulunderwood Wagstaff PRP Search 7 2020-08-18 22:15
I found the primality test, there seems to be no composite numbers that pass the test sweety439 sweety439 7 2020-02-11 19:49
500€ Reward for a proof for the Wagstaff primality test conjecture Tony Reix Wagstaff PRP Search 7 2013-10-10 01:23
Wagstaff number primality test? ixfd64 Math 12 2010-01-05 16:36
PRIMALITY PROOF for Wagstaff numbers! AntonVrba Math 96 2009-02-25 10:37

All times are UTC. The time now is 20:51.


Wed Dec 1 20:51:01 UTC 2021 up 131 days, 15:20, 1 user, load averages: 1.52, 1.48, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.