mersenneforum.org A new Wagstaff primality test ?
 Register FAQ Search Today's Posts Mark Forums Read

 2021-11-25, 17:46 #1 kijinSeija   Mar 2021 France 2×32 Posts 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 :)
2021-11-25, 18:41   #2
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

153010 Posts

Quote:
 Originally Posted by kijinSeija 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:)

2021-11-26, 05:21   #3
paulunderwood

Sep 2002
Database er0rr

23·7·71 Posts

Quote:
 Originally Posted by kijinSeija 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

 2021-11-26, 13:12 #4 kijinSeija   Mar 2021 France 2×32 Posts 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.
2021-11-26, 15:13   #5
paulunderwood

Sep 2002
Database er0rr

23×7×71 Posts

Quote:
 Originally Posted by paulunderwood 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

 2021-11-26, 20:47 #6 kijinSeija   Mar 2021 France 2·32 Posts 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
2021-11-26, 21:04   #7
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·32·5·17 Posts

Quote:
 Originally Posted by kijinSeija 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).

2021-11-27, 13:43   #8
kijinSeija

Mar 2021
France

1810 Posts

Quote:
 Originally Posted by R. Gerbicz 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Wagstaff PRP Search 7 2020-08-18 22:15 sweety439 sweety439 7 2020-02-11 19:49 Tony Reix Wagstaff PRP Search 7 2013-10-10 01:23 ixfd64 Math 12 2010-01-05 16:36 AntonVrba Math 96 2009-02-25 10:37

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

Tue Jan 18 00:51:12 UTC 2022 up 178 days, 19:20, 0 users, load averages: 0.77, 1.02, 1.06