- **Wagstaff PRP Search**
(*https://www.mersenneforum.org/forumdisplay.php?f=102*)

- - **A new Wagstaff PRP test ?**
(*https://www.mersenneforum.org/showthread.php?t=27352*)

A new Wagstaff PRP 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. |

fixFor 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 wagstafft3(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] |

All times are UTC. The time now is 20:55. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.