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]

Maybe I found a probable primality test than works for Wagstaff and Mersenne primes with the same conditions :

Let [TEX]$N = \frac{-a^p-1}{-a-1}$[/TEX] with a = 2 for Wagstaff numbers and a= -2 for Mersenne Numbers

Let the sequence [TEX]S_i = 2 \cdot T_{|a|}(S_{i-1}/2)[/TEX] where [TEX]T_{n}(x)[/TEX] is the Chebyshev's polynomial of the first kind with [TEX]$S_0 = 3$[/TEX]

[TEX]$N$[/TEX] is prime if [TEX]S_{p-1} \equiv 2 \cdot T_{|a|-(-|a|/a)-(-1)^{((p-|a|/a)/2)}}(3/2) (mod N)[/TEX]

You can run the test here : [url]https://sagecell.sagemath.org/?z=eJxtj7FuxCAQRPuT7h9WrhYH5ECKFGTzB3Hj9nQS9nEyEj6QIYny91n7ohRRGmYYDQ-NI2UsnE7QOiAwkFZQpj0eMunne768lwqjh7yGxYO7XeAVtkZPqNw5Ky06Niz2eIj0xOdAb-mCUfZbNNWVNOvnHKJHvr1QlgOZNqc4zX78KrP_QDcWdEJqOXRGWG490A4smmK4VtyAg_r3keLfd9PtXoszYlb4mwkmMjhu0osNGq7IXHqUPOlW8c8MYe9xsw9uxE-rmdKSUwmVI2G_AQMYVjg=&lang=gp&interacts=eJyLjgUAARUAuQ==[/url]

Do you think if it's possible to prove it ? It was provable for the classic Lucas-Lehmer test, so maybe it is provable with this test too, I didn't found any counterexample for the moment :smile:

[QUOTE=kijinSeija;611393]Maybe I found a probable primality test than works for Wagstaff and Mersenne primes with the same conditions :

Let [TEX]$N = \frac{-a^p-1}{-a-1}$[/TEX] with a = 2 for Wagstaff numbers and a= -2 for Mersenne Numbers

Let the sequence [TEX]S_i = 2 \cdot T_{|a|}(S_{i-1}/2)[/TEX] where [TEX]T_{n}(x)[/TEX] is the Chebyshev's polynomial of the first kind with [TEX]$S_0 = 3$[/TEX]

[TEX]$N$[/TEX] is prime if [TEX]S_{p-1} \equiv 2 \cdot T_{|a|-(-|a|/a)-(-1)^{((p-|a|/a)/2)}}(3/2) (mod N)[/TEX]

Do you think if it's possible to prove it ? It was provable for the classic Lucas-Lehmer test, so maybe it is provable with this test too, I didn't found any counterexample for the moment :smile:[/QUOTE]
Interesting.
I'll have a deeper look asap.
Maybe you could replace all "-" signs in N by "+" signs.
And give details about each of Wagstaff and Mersenne cases: computed values for small p and the complete and simplified formula for each case.
How far did you test?
(I have no PC with me now)

For Wagstaff Numbers :

[CODE]
? forprime(q=3,200, print(t(q)))
q:3 ,w: 3
s1=0

q:5 ,w: 11
s1=0

q:7 ,w: 43
s1=0

q:11 ,w: 683
s1=0

q:13 ,w: 2731
s1=0

q:17 ,w: 43691
s1=0

q:19 ,w: 174763
s1=0

q:23 ,w: 2796203
s1=0

q:29 ,w: 178956971
s1=35462304

q:31 ,w: 715827883
s1=0

q:37 ,w: 45812984491
s1=22633578773

q:41 ,w: 733007751851
s1=237058155852

q:43 ,w: 2932031007403
s1=0

q:47 ,w: 46912496118443
s1=43837675287567

q:53 ,w: 3002399751580331
s1=2323597922301294

q:59 ,w: 192153584101141163
s1=43405475675237573

q:61 ,w: 768614336404564651
s1=0

q:67 ,w: 49191317529892137643
s1=18491486101210104962

q:71 ,w: 787061080478274202283
s1=672936394093447809238

q:73 ,w: 3148244321913096809131
s1=1795244001282278966829

q:79 ,w: 201487636602438195784363
s1=0

q:83 ,w: 3223802185639011132549803
s1=575962240197809829006347

q:89 ,w: 206323339880896712483187371
s1=101697903320160405940678618

q:97 ,w: 52818775009509558395695966891
s1=47418661886717800473597639812

q:101 ,w: 845100400152152934331135470251
s1=0

q:103 ,w: 3380401600608611737324541881003
s1=2163853741122871996993570309177

q:107 ,w: 54086425609737787797192670096043 s1=40984583554059445857015264239417

q:109 ,w: 216345702438951151188770680384171 s1=48553388173305748538138563460025

q:113 ,w: 3461531239023218419020330886146731 s1=1501577949756601699943132034371628

q:127 ,w: 56713727820156410577229101238628035243
s1=0

q:131 ,w: 907419645122502569235665619818048563883 s1=675255604002653037167762564789642028717

q:137 ,w: 58074857287840164431082599668355108088491
s1=29782361227426807280197948853870970493442

q:139 ,w: 232299429151360657724330398673420432353963 s1=180823998115931831437870551556753357923954

q:149 ,w: 237874615450993313509714328241582522730457771 s1=26502703015677001084529847262630194280688763

q:151 ,w: 951498461803973254038857312966330090921831083 s1=767834026054558051499460097360371231864912320

q:157 ,w: 60895901555454288258486868029845125818997189291 s1=22758383762731006210941976567879889094160008662

q:163 ,w: 3897337699549074448543159553910088052415820114603 s1=3147755244116520759735228945070115202448119192873

q:167 ,w: 62357403192785191176690552862561408838653121833643
s1=0

q:173 ,w: 3990873804338252235308195383203930165673799797353131 s1=3773380018331381359874134732369509944603170792643824

q:179 ,w: 255415923477648143059724504525051530603123187030600363 s1=90278170195369259663664519328330687398992158859609666

q:181 ,w: 1021663693910592572238898018100206122412492748122401451 s1=25275761152202162177068118911776013172313057421921272

q:191 ,w: 1046183622564446793972631570534611069350392574077339085483
s1=0

q:193 ,w: 4184734490257787175890526282138444277401570296309356341931 s1=490498661136809600403936047657568663261295050600166752926

q:197 ,w: 66955751844124594814248420514215108438425124740949701470891 s1=35495427703180153027963472585444260458023196834276102776577

q:199 ,w: 267823007376498379256993682056860433753700498963798805883563
s1=0
[/CODE]

For Mersenne numbers :

[CODE]
? forprime(q=3,200, print(t(q)))
q:3 ,w: 7
s1=0

q:5 ,w: 31
s1=0

q:7 ,w: 127
s1=0

q:11 ,w: 2047
s1=1607

q:13 ,w: 8191
s1=0

q:17 ,w: 131071
s1=0

q:19 ,w: 524287
s1=0

q:23 ,w: 8388607
s1=815074

q:29 ,w: 536870911
s1=289611393

q:31 ,w: 2147483647
s1=0

q:37 ,w: 137438953471
s1=62131939238

q:41 ,w: 2199023255551
s1=143549775376

q:43 ,w: 8796093022207
s1=7551383590233

q:47 ,w: 140737488355327
s1=52891699560247

q:53 ,w: 9007199254740991
s1=8366824338705290

q:59 ,w: 576460752303423487
s1=358615917252629447

q:61 ,w: 2305843009213693951
s1=0

q:67 ,w: 147573952589676412927
s1=67009295408650361316

q:71 ,w: 2361183241434822606847
s1=1735688411577756295226

q:73 ,w: 9444732965739290427391
s1=30922976274147574010

q:79 ,w: 604462909807314587353087
s1=290547409084571062280606

q:83 ,w: 9671406556917033397649407
s1=2165342894805439856382527

q:89 ,w: 618970019642690137449562111
s1=0

q:97 ,w: 158456325028528675187087900671
s1=31771632134636405756544106260

q:101 ,w: 2535301200456458802993406410751
s1=1336439533263272606812194950146

q:103 ,w: 10141204801825835211973625643007
s1=1509296843045822788662294171957

q:107 ,w: 162259276829213363391578010288127
s1=0

q:109 ,w: 649037107316853453566312041152511
s1=556884570374941377547115102393166

q:113 ,w: 10384593717069655257060992658440191
s1=5068074721493003956791340784974471

q:127 ,w: 170141183460469231731687303715884105727
s1=0

q:131 ,w: 2722258935367507707706996859454145691647
s1=1516757122616911896094254191049737051849

q:137 ,w: 174224571863520493293247799005065324265471
s1=163842583007416170909821893382414965645556

q:139 ,w: 696898287454081973172991196020261297061887
s1=46705198311407299245440149148266534783772

q:149 ,w: 713623846352979940529142984724747568191373311
s1=561891623480948338529701112067154730490230926

q:151 ,w: 2854495385411919762116571938898990272765493247
s1=2829464711188493325175801501249655843781087386

q:157 ,w: 182687704666362864775460604089535377456991567871
s1=100673681739430680947486076923530912740937570376

q:163 ,w: 11692013098647223345629478661730264157247460343807
s1=11368492991431645161264116930802833588285449233837

q:167 ,w: 187072209578355573530071658587684226515959365500927
s1=30366014861212227154107279163299712464685645481638

q:173 ,w: 11972621413014756705924586149611790497021399392059391
s1=3258300855337674590876910647524040908033118687155945

q:179 ,w: 766247770432944429179173513575154591809369561091801087
s1=88996800370430364572446925655732968627245182062583665

q:181 ,w: 3064991081731777716716694054300618367237478244367204351
s1=2873106258197702872144284527457473447108057424250030158

q:191 ,w: 3138550867693340381917894711603833208051177722232017256447
s1=782801006335836471924253266478273673553323419418577508933

q:193 ,w: 12554203470773361527671578846415332832204710888928069025791
s1=510009340455423487745953843163838674653030967481885342349

q:197 ,w: 200867255532373784442745261542645325315275374222849104412671
s1=177512020029058784941440331206388581089073179204650354567171

q:199 ,w: 803469022129495137770981046170581301261101496891396417650687
s1=229107978040452740359342358033137472971457177405266811118373
[/CODE]

I checked until p = 1000 and I didn't find counterexample. I will check higher later.

For the code I used this one on Pari GP [CODE]t(q)={a=-2;w=(-a^q-1)/(-a-1);l=3;S0=2*polchebyshev(abs(a),1,l/2);print("q:",q," ,w: ",w);S=S0;for(i=1,q-1,S=Mod(sum(k=0, floor(abs(a)/2), (-1)^k*abs(a)/(abs(a)-k)*binomial(abs(a)-k,k)*(S)^(abs(a)-2*k)) ,w));s1=lift(Mod(S-2*polchebyshev(abs(a)-(-abs(a)/a)-(-1)^((q-(abs(a)/a))/2),1,l/2),w));print(" s1=",s1)}[/CODE]

I use Chebyshev functions instead of S^2-2, because I check some Generalized Wagstaff and Mersenne numbers (a^p-1)/(a-1) and (a^p+1)/(a+1)

[TEX]S_{0} = 7[/TEX] not [TEX]3[/TEX] sorry for the mistake

That reminds me this: [url]https://arxiv.org/pdf/2010.02677.pdf[/url]