mersenneforum.org A new Wagstaff PRP test ?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2022-02-09, 01:28 #12 JCoveiro   "Jorge Coveiro" Nov 2006 Moura, Portugal 4810 Posts 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,
 2022-02-09, 01:54 #13 JCoveiro   "Jorge Coveiro" Nov 2006 Moura, Portugal 24×3 Posts 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, 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, Last fiddled with by JCoveiro on 2022-02-09 at 02:00
 2022-08-14, 15:37 #14 kijinSeija   Mar 2021 France 1100102 Posts Maybe I found a probable primality test than works for Wagstaff and Mersenne primes with the same conditions : Let $N = \frac{-a^p-1}{-a-1}$ with a = 2 for Wagstaff numbers and a= -2 for Mersenne Numbers Let the sequence $S_i = 2 \cdot T_{|a|}(S_{i-1}/2)$ where $T_{n}(x)$ is the Chebyshev's polynomial of the first kind with $S_0 = 3$ $N$ is prime if $S_{p-1} \equiv 2 \cdot T_{|a|-(-|a|/a)-(-1)^{((p-|a|/a)/2)}}(3/2) (mod N)$ You can run the test here : https://sagecell.sagemath.org/?z=eJx...yLjgUAARUAuQ== 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
2022-08-15, 14:47   #15
T.Rex

Feb 2004
France

16458 Posts

Quote:
 Originally Posted by kijinSeija Maybe I found a probable primality test than works for Wagstaff and Mersenne primes with the same conditions : Let $N = \frac{-a^p-1}{-a-1}$ with a = 2 for Wagstaff numbers and a= -2 for Mersenne Numbers Let the sequence $S_i = 2 \cdot T_{|a|}(S_{i-1}/2)$ where $T_{n}(x)$ is the Chebyshev's polynomial of the first kind with $S_0 = 3$ $N$ is prime if $S_{p-1} \equiv 2 \cdot T_{|a|-(-|a|/a)-(-1)^{((p-|a|/a)/2)}}(3/2) (mod N)$ 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
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)

Last fiddled with by T.Rex on 2022-08-15 at 14:48

 2022-08-15, 15:47 #16 kijinSeija   Mar 2021 France 2·52 Posts 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 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 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)} 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) Last fiddled with by kijinSeija on 2022-08-15 at 15:50
 2022-08-15, 21:15 #17 kijinSeija   Mar 2021 France 628 Posts $S_{0} = 7$ not $3$ sorry for the mistake Last fiddled with by kijinSeija on 2022-08-15 at 21:16
 2022-08-16, 07:47 #18 T.Rex     Feb 2004 France 16458 Posts That reminds me this: https://arxiv.org/pdf/2010.02677.pdf Last fiddled with by T.Rex on 2022-08-16 at 07:47
 2022-08-20, 21:23 #19 kijinSeija   Mar 2021 France 628 Posts New property ? Maybe I found a new property about the Reix conjecture : Let $W_p = (2^p+1)/3$ where $p$ is a prime number $>3$ Let the sequence $S_i = S_{i-1}^2-2$ with $S_0 = 1/4 = (2^{(p-2)}+1)/3$ $W_p$ is prime if $S_{p-2} \equiv (W_p-1)/2+2 \equiv 2 \cdot S_0 + 1$ The Pari GP code to check the conjecture : Code:  t(q)={w=(2^q+1)/3;S0=1/4;print("w: ",w);S=S0;for(i=1,q-2,S=Mod(S^2-2,w));s1=lift(Mod(S-((w-1)/2+2),w));print(s1," ")} ? forprime(q=3,200,(t(q))) q: 3 w: 3 2 q: 5 w: 11 0 q: 7 w: 43 0 q: 11 w: 683 0 q: 13 w: 2731 0 q: 17 w: 43691 0 q: 19 w: 174763 0 q: 23 w: 2796203 0 q: 29 w: 178956971 148328604 q: 31 w: 715827883 0 q: 37 w: 45812984491 24013210652 q: 41 w: 733007751851 578666895402 q: 43 w: 2932031007403 0 q: 47 w: 46912496118443 45479133625061 q: 53 w: 3002399751580331 582220641320127 q: 59 w: 192153584101141163 149471670618762341 q: 61 w: 768614336404564651 0 q: 67 w: 49191317529892137643 29433794893490190258 q: 71 w: 787061080478274202283 341602215950445231784 q: 73 w: 3148244321913096809131 2588298572977432531241 q: 79 w: 201487636602438195784363 0 q: 83 w: 3223802185639011132549803 2941972935918702317448471 q: 89 w: 206323339880896712483187371 66974682110145709677667101 q: 97 w: 52818775009509558395695966891 49692803662195088107287524127 q: 101 w: 845100400152152934331135470251 0 q: 103 w: 3380401600608611737324541881003 1617593003444420535702916633129 q: 107 w: 54086425609737787797192670096043 5672753555637487782056481655731 q: 109 w: 216345702438951151188770680384171 194118643299931373894593838136116 q: 113 w: 3461531239023218419020330886146731 1019543448087266479215549595100475 q: 127 w: 56713727820156410577229101238628035243 0 q: 131 w: 907419645122502569235665619818048563883 314277216384605587120839967100937178478 q: 137 w: 58074857287840164431082599668355108088491 24778318022691375721663916596760266302224 q: 139 w: 232299429151360657724330398673420432353963 57382243707830577855987457895453136163716 q: 149 w: 237874615450993313509714328241582522730457771 93176910676270118136233263825222545067689724 q: 151 w: 951498461803973254038857312966330090921831083 648060689992125350030081556538812233582203959 q: 157 w: 60895901555454288258486868029845125818997189291 35630434179621771049596888226219699913450832505 q: 163 w: 3897337699549074448543159553910088052415820114603 2317790472758544518337676019136175860599583513335 q: 167 w: 62357403192785191176690552862561408838653121833643 0 q: 173 w: 3990873804338252235308195383203930165673799797353131 371011654722662023999926776710944629956493639282711 q: 179 w: 255415923477648143059724504525051530603123187030600363 55745571531645367720541050873662338089610309630076893 q: 181 w: 1021663693910592572238898018100206122412492748122401451 1009891773589539741838500595408129006958987617245584039 q: 191 w: 1046183622564446793972631570534611069350392574077339085483 0 q: 193 w: 4184734490257787175890526282138444277401570296309356341931 3928658498611840039653581597148870081532859834159865883500 q: 197 w: 66955751844124594814248420514215108438425124740949701470891 7375405652987315748567955736547475635383458586082124230435 q: 199 w: 267823007376498379256993682056860433753700498963798805883563 0 I don't know if T.Rex has noticed that before, we now have something for the conjecture for $S_{p-2}$, like the Lucas-Lehmer test for Mersenne numbers.
 2022-08-21, 18:53 #20 kijinSeija   Mar 2021 France 2·52 Posts Inspired by Reix conjecture, I think I found a formula that divides only Wagstaff primes numbers and not the composite Wagstaff numbers : The formula is : $G_n = 4^{2^n} \cdot ((1/8 - 1/8 (3 i sqrt(7)))^{(2^n)} + (1/8 + 1/8 (3 i sqrt(7)))^{(2^n)}) + 3$ And it seems than $W_q$ is prime only if it divides $G_{q-2}$ when q > 3 For example : G_3 = 70532 and it divides W_5 = 11 G_5 = -23820962743960351228 and it divides W_7 = 43 G_7 doesn't divide W_9 = 171 G_9 divides W_11 = 683 G_11 divides W_13 = 2731 G_13 doesn't divides W_15 = 10923 G_15 divides W_17 = 43691 G_17 divides W_19 Etc. It looks like the Lucas-Lehmer test can works with the seed 1/4 Last fiddled with by kijinSeija on 2022-08-21 at 18:54
 2022-08-25, 13:22 #21 kijinSeija   Mar 2021 France 5010 Posts New formula I checked with this formula $\omega = (\frac{1}{2} (1 + i \sqrt7))^{(\frac{2^{p - 1} - 1}{3})} + (\frac{1}{2} (1 - i \sqrt7))^{(\frac{2^{p - 1} - 1}{3})}$ And it seems than $\omega \equiv 0 (mod W_p)$ only if $W_p$ is prime but the numbers of the formula are growing very fast so I can't check for big numbers. For p>3 But maybe this is promising, let's find a sequence now if it possible. Last fiddled with by kijinSeija on 2022-08-25 at 13:31
 2023-01-01, 23:07 #22 kijinSeija   Mar 2021 France 2×52 Posts Lucas-Lehmer test using 2^p+1 for Wagstaff numbers Hello All the last test were using $P=(2^p+1)/3$ but $P-1$ and $P+1$ can't be factorised easily, so apparently LLT can't be used, I read that from some papers (I don't really understand that, if someone can explain me this, it would be very nice ) But I tried some new test with $P=2^p+1$ for testing if Wagstaff numbers are probable prime and I found maybe something interesting : Let $Np=2^p+1$ and $Wp=(2^p+1)/3$ for Wagstaff numbers with $p$ a prime number $> 3$. Then $W_p$ is prime if $S_{p-2} \equiv 10 \cdot S_0 - 1 (mod N_p)$ and $p \equiv 2 (mod 3)$ or $S_{p-2} \equiv 2 \cdot S_0 + 1 (mod N_p)$ and $p \equiv 1 (mod 3)$ for example with $p = 17$ we get this on PARI/GP : Code:  Mod(10923, 131073) Mod(35497, 131073) Mod(32258, 131073) Mod(121088, 131073) Mod(84743, 131073) Mod(17450, 131073) Mod(19919, 131073) Mod(8588, 131073) Mod(90716, 131073) Mod(105422, 131073) Mod(118412, 131073) Mod(129713, 131073) Mod(14576, 131073) Mod(121514, 131073) Mod(16598, 131073) Mod(109229, 131073) $17 \equiv 2 (mod 3)$ and we get $10 \cdot (2^{17-2}+1)/3 - 1$ at the last residue and $(2^{17}+1)/3 = 43691$ and this is indeed prime. This is interesting because $N_p - 1$ is can be factorised easily (so LLT can be used ?) I have checked until p = 10000 and I didn't find any counterexamples and I have checked with higher Wagstaff exponent too and it seems it works. Do you think it's easier to prove it when you can use P-1 as a modulo for the test ? Thanks in advance

 Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Wagstaff PRP Search 10 2022-03-31 04:19 GP2 Wagstaff PRP Search 414 2020-12-27 08:11 Tony Reix Wagstaff PRP Search 7 2013-10-10 01:23 Batalov GMP-ECM 9 2012-08-24 10:26 ixfd64 Math 12 2010-01-05 16:36

All times are UTC. The time now is 17:19.

Mon Feb 6 17:19:47 UTC 2023 up 172 days, 14:48, 1 user, load averages: 0.76, 1.01, 1.03

Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔