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

112×13 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

420210 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 368 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

101528 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 111102 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

112·13 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

2·3·5 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.

 2022-02-08, 15:23 #9 JCoveiro   "Jorge Coveiro" Nov 2006 Moura, Portugal 608 Posts 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
 2022-02-08, 16:04 #10 JCoveiro   "Jorge Coveiro" Nov 2006 Moura, Portugal 1100002 Posts 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,
 2022-02-08, 16:08 #11 JCoveiro   "Jorge Coveiro" Nov 2006 Moura, Portugal 4810 Posts 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,

 Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Wagstaff PRP Search 10 2022-03-31 04:19 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 14:28.

Mon Jun 27 14:28:56 UTC 2022 up 74 days, 12:30, 2 users, load averages: 0.70, 0.86, 0.99