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 :)

[QUOTE=kijinSeija;593878]This is a viable test or not ?
Thanks :)[/QUOTE]

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:)

[QUOTE=kijinSeija;593878]

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 ?

[/QUOTE]

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;
[/code]

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.

[QUOTE=paulunderwood;593921]

[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;
[/code][/QUOTE]

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.

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 [url]https://oeis.org/A028491[/url] 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

[QUOTE=kijinSeija;593941]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.[/QUOTE]

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).

[QUOTE=R. Gerbicz;593974]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).[/QUOTE]

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.

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,[/CODE]

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,[/CODE]

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,[/CODE]

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,[/CODE]

more wagstaff simplifications
 

t3(q)={w=(2^q+1)/3;s=4;for(i=1,q,s=(s^2-2)%(6*w););if(s==14||s==194,print1(q","))}
forprime(x=1,100000,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,[/CODE]

more simplifications (2)
 

t3(q)={w=(2^q+1)/3;s=4;for(i=2,q,s=(s^2-2)%(6*w));if(ispowerful(s+2),print1(q","))}
forprime(x=1,1000,t3(x))

[CODE]3,5,7,11,13,17,19,23,31,43,61,79,101,127,167,191,199,313,347,701,[/CODE]

or

t3(q)={w=(2^q+1)/3;s=4;for(i=2,q,s=(s^2-2)%(6*w));if(issquare(s+2),print1(q","))}
forprime(x=1,1000,t3(x))

[CODE]3,5,7,11,13,17,19,23,31,43,61,79,101,127,167,191,199,313,347,701,[/CODE]