New Wagstaff PRP exponents
Hello,
I believe I have found the two largest known Wagstaff primes, after Tony Reix's discovery of (2^4031399+1)/3. Here they are: [code](2^13347311 + 1)/3 is 3PRP! (16355.1659s+0.0028s)[/code] and: [code](2^13372531 + 1)/3 is 3PRP! (34165.4750s+0.0029s)[/code] Each is a probable prime with about 4 million decimal digits. Can anyone with some spare cycles help verify these using PFGW or other primality testing software? Thanks!  Ryan 
Congratulations!
You can: * try the VrbaReix as implemented in LLR (you have to modify llr.ini) * also run pfgw with b5, b7 (and another dozen bases). * and run pfgw with t, tp and tc. I'll run a few of these for you, in parallel. 
Wowee! :w00t:

What ranges did you search, Ryan?

Finding 2 close to each other, similar like how things work in Mersenne sometimes,
Maybe the odds for finding a Wagstaff in range [n;2n] which seemed a diverging sequence, so odds getting slowly a tad less each doubling of n, maybe maybe this is odds it's converging towards a near similar chance like one has to find a Mersenne. Note that TF and P1 rates of Wagstaff are considerable better than for Mersenne, so when i say 'converging towards' i still mean a considerable worse chance in range [n;2n], yet not as bad as the real small odds it seemed like considering the previous 2 were just under a million and something in the 4 million bits. Moving towards the 4 million is factor 4+, then suddenly 2 at 13 million is factor 3, yet there is 2, where there is 2 there could be more. So that's pretty good news, of course assuming both are PRP! 
Prime95 concur on the first one:
2^13347311+1/3 is a probable prime! We4: B33A699A,00000000 
A Hearty congratulations to the project! Thanks especially to Tony Reix, Paul Underwood, and Vincent Diepeveen for testing so many candidates over the years. I am surprised that it took until now for Five or Bust to lose its lock on the largest known probable prime (since January 2009), but apparently the Wagstaff search hit a fairly substantial gap.
If these were proven primes, they would come in at 11th and 12th largest known, just below the 39th Mersenne and just above the last discovery of Seventeen or Bust. [QUOTE=diep;352449] Note that TF and P1 rates of Wagstaff are considerable better than for Mersenne[/QUOTE] Do you have any statistics supporting this? I'm not saying it is wrong, just that I would expect the rates to be very similar. 
[QUOTE=philmoore;352540]A Hearty congratulations to the project! Thanks especially to Tony Reix, Paul Underwood, and Vincent Diepeveen for testing so many candidates over the years. I am surprised that it took until now for Five or Bust to lose its lock on the largest known probable prime (since January 2009), but apparently the Wagstaff search hit a fairly substantial gap.
If these were proven primes, they would come in at 11th and 12th largest known, just below the 39th Mersenne and just above the last discovery of Seventeen or Bust. Do you have any statistics supporting this? I'm not saying it is wrong, just that I would expect the rates to be very similar.[/QUOTE] Jeff Gilchrist did do lately really a lot of work. Interesting is to know what range was checked and what TF was done to find these 2 and whether a similar algorithm was used that was used to find some of the largest Mersennes past few years, prioritizing which exponent to use based upon factorisation of N+1 and N1 of the exponent. As for the TF and P1, i tend to remember posts that Mersenne TF'ed roughly 50% and that P1 removed roughly 7.5%. Please correct that if it's different. For Wagstaff even a quick TF already removes 60% and with gpu's add another 10% and P1 removes also 10%. The overlap of deeper TF and P1 is not so large. So in total you look at a 7075% that gets removed pretty easily with far less computational effort than has been done for Mersenne with respect to the P1. More accurate statistics will be there in some months hopefully with gpu factorisation stats. It's been some years i datamined through Mersenne statistics there. Can't remember how shallow those were compared to what we're doing. Note that Mersenne is a 1 formula and that Wagstaff is a +1 formula which should already explain a lot. Mersenne give a reasonable steady number of primes in each given range just like 3 * 2^n  1 also does. Wagstaff so far was pretty much a gamble whether it would be converging or diverging or constant in odds to the next PRP. I would guess blindfolded doing factorisation attempts other than P1 to remove some composites from Wagstaffs list to be tested might be more succesful than for Mersenne. In all cases and with respect to any statement the important emphasis is on the word "similar". Even if something factors 1% better i would not consider that similar. 
I just finished both exponents with LLR and they also show as PRP:
[CODE](2^13347311+1)/3 is VrbaReix PRP! Time : 56958.781 sec. (2^13372531+1)/3 is VrbaReix PRP! Time : 57032.491 sec. [/CODE] Good find. 
[QUOTE=diep;352543]Jeff Gilchrist did do lately really a lot of work.
Interesting is to know what range was checked and what TF was done to find these 2 and whether a similar algorithm was used that was used to find some of the largest Mersennes past few years, prioritizing which exponent to use based upon factorisation of N+1 and N1 of the exponent.[/QUOTE] Yes, I am indebted to Jeff's prior work here as well. For my part, I started with the first 25,000 prime exponents from each of q=10e6, 11e6, 12e6 and 13e6. A large fraction of these were weeded out by a very basic program I wrote to do simple trial factoring up to d=1000, then many more by PFGW's own trial factoring. I'll have to do a bit of work to determine exactly how many exponents were fully tested by PFGW. 
Note that for the pfgw trial factoring you would want to use something like this command line:
[B]pfgw f{13372607*2,1} q(2^13372607+1)/3[/B] [B](2^13372607+1)/3 has factors: 50253508240009[/B] (this will only look for factors of form 2*p*k+1) Compare the running time of the above to this: [B]pfgw f q(2^13372607+1)/3[/B] ____________________________________ P.S. The VrbaReix tests and some LLR and PFGW tests in a bunch of bases on the same two exponents are almost done here, too. 
[QUOTE=ryanp;352547]Yes, I am indebted to Jeff's prior work here as well. For my part, I started with the first 25,000 prime exponents from each of q=10e6, 11e6, 12e6 and 13e6. A large fraction of these were weeded out by a very basic program I wrote to do simple trial factoring up to d=1000, then many more by PFGW's own trial factoring. I'll have to do a bit of work to determine exactly how many exponents were fully tested by PFGW.[/QUOTE]
Your part? Are you part of a larger group of people working on this? Has anyone worked on anything less than 10e6? What ranges are you actively working on now and how much CPU power are you throwing at this? Jeff. 
Congratulations !
Waowwww ! Two new Wagstaff PRPs !! :smile: :bow: :smile: :razz: :smile: :w00t: :smile:
That's tremendous, wonderful, extraordinary, etc. I'm missing (english) words ! The sad side of this nice story is that my own Wagstaff PRP now looks quite small... :sad: Moreover, Diep, Jeff, and Paul spent a lot of time looking for such a Wagstaff PRP with no luck up to now. :sad: I hope that they will have some success some day. :smile: They deserve it. So, now we need someone to provide a proof of VrbaReix conjecture ! :razz: so that PRPs become true primes ! I hope to see that before I die. Some years ago, I promissed 100€ for such a proof. Now, I would give 200€. Anyone to contribute and add some € or $ to build a reward ? :wink: On my side, I'm now making photographs: [url]http://500px.com/Tony_Reix[/url] [url]www.tonyfcr.book.fr/[/url] that's fun too ! Regards Tony 
It looks like Ryan holds the current record for the ECM largest factor [I]and[/I] the largest Wagstaff PRP. Really impressive, to say the least. Now all he's missing is a new Mersenne prime. xD
Also, welcome back, Tony! :smile: 
2nd exponent in Prime95:
2^13372531+1/3 is a probable prime! We4: E3ACC173,00000000 
Serge should be giving some PRP results soon.
I have started a GMP implementation of my test for the new Wagstaffs on a Q6600: (L+2)^(N+1)==5 (mod N, L^2+1) It will take a few weeks :smile: 
Sounds like a race, Paul. I started my machine on SPSP2, ES Lucas, and your Frobenius test yesterday for both numbers. As you say, it will take a long time as they're generic tests using GMP.

I have a special version that calculates modulo 2^p+1  so no generic modulo. :smile:

[QUOTE=danaj;352638]Sounds like a race, Paul. I started my machine on SPSP2, ES Lucas, and your Frobenius test yesterday for both numbers. As you say, it will take a long time as they're generic tests using GMP.[/QUOTE]
SPSP2 will always pass for Wagstaff numbers? 2^p = 1 (mod 2^p+1) => 2^p = 1 (mod (2^p+1)/3) 
[QUOTE=ATH;352655]SPSP2 will always pass for Wagstaff numbers?[/quote]That is my understanding and I debated whether to start them or not, but I thought it wouldn't hurt and since it should finish first, will give me some idea of when the Lucas and Frobenius tests will be done. It'll be a long wait...

[CODE](2^13347311+1)/3 is Base 27  Strong Fermat PRP! Time : 132008.336 sec.
(2^13347311+1)/3 is VrbaReix PRP! Time : 131975.246 sec. (2^13372531+1)/3 is Base 27  Strong Fermat PRP! Time : 132322.407 sec. (2^13372531+1)/3 is VrbaReix PRP! Time : 132513.794 sec. (2^13347311+1)/3 is 5PRP! (229303.3908s+398.4266s) (2^13347311+1)/3 is 7PRP! (277072.1587s+419.3222s) (2^13347311+1)/3 is 11PRP! (291376.7357s+419.8591s) (2^13347311+1)/3 is 13PRP! (291281.3062s+418.0968s) (2^13347311+1)/3 is 17PRP! (278100.7506s+382.4561s) (2^13372531+1)/3 is 5PRP! (249353.0860s+421.2026s) (2^13372531+1)/3 is 7PRP! (229612.6239s+399.1560s) (2^13372531+1)/3 is 11PRP! (230611.3771s+399.9541s) (2^13372531+1)/3 is 13PRP! (231212.1002s+401.6447s) (2^13372531+1)/3 is 17PRP! (230925.5544s+399.9358s) # tests for false positives below  (2^13372309+1)/3 is not prime. RES64: 991A9DB47059EE26. OLD64: D0794CB28426C889 Time : 132114.403 sec. (2^13372309+1)/3 is not prime. VrbaReix RES64: FE684FD81D62F060 Time : 132268.574 sec. # b5 (2^13372309+1)/3 is composite: RES64: [E9EDD6FC780DA64D] (225266.1438s+403.6897s) # b3 (2^13372309+1)/3 is composite: RES64: [FA860AF0EE31F99B] (230901.3211s+404.2113s) # b2 (2^13372309+1)/3 is 2PRP! (225516.2154s+403.9142s)[/CODE] 
[QUOTE]Running N+1 test using discriminant 2, base 1+sqrt(2)
Generic modular reduction using allcomplex AVX FFT length 768K, Pass1=256, Pass 2=3K on (2^13372531+1)/3 Calling BrillhartLehmerSelfridge with factored part 0.00% (2^13372531+1)/3 is Lucas PRP! (851290.8327s+0.0578s) [/QUOTE] I lost the other test on (2^13347311+1)/3 on the way, 10 days is a long time without any intermediate savefiles. Several other people seems to have these test running on faster computers than mine though, so I didn't restart it. 
[QUOTE=ATH;353497]I lost the other test on (2^13347311+1)/3 on the way, 10 days is a long time without any intermediate savefiles. Several other people seems to have these test running on faster computers than mine though, so I didn't restart it.[/QUOTE]
:tu: I've got 'em covered. One more day to go on a 4770k at 4GHz. 
[CODE]Running N+1 test using discriminant 2, base 1+sqrt(2)
(2^13347311+1)/3 is Lucas PRP! (442900.4907s+0.0204s) [/CODE] and confirming ATH's result: [CODE]Running N+1 test using discriminant 2, base 1+sqrt(2) (2^13372531+1)/3 is Lucas PRP! (443577.1559s+0.0284s) [/CODE] The tests for (L+2)^(n+1)==5 (mod n, L^2+1) will take another 3 to 4 weeks :smile: 
[QUOTE=paulunderwood;353645]
The tests for (L+2)^(n+1)==5 (mod n, L^2+1) will take another 3 to 4 weeks :smile:[/QUOTE] The tests passed for both PRPs. :smile: I have emailed Henri Lifchitz requesting that the annotations for the PRPs in [URL="http://www.primenumbers.net/prptop/prptop.php"]his database[/URL] lists all our PRP tests. 
[QUOTE=paulunderwood;353645]The tests for (L+2)^(n+1)==5 (mod n, L^2+1) will take another 3 to 4 weeks :smile:[/QUOTE]
Sorry for my ignorance but n is the Wagstaff PRP right, but what is L ? and what is meant by "n, L^2 +1" in the modular expression? My guess is that (L+2)^(n+1)==5 for both (mod n) and (mod L^2+1) ? (and yes I did spend a bit of time looking for an answer myself, before I get told to study myself :) But not too much since it is not [I]that[/I] important) 
The modular reduction is done over "n" and "L^2+1". Here is a worked example for n=11 where L^2==1 (mod 11, L^2+1)
[CODE] (L+2)^2==L^2+4*L+4==4*L+3 (L+2)^3==(4*L+3)*(L+2)==4*L^2+11*L+6==0*L+64==2 (L+2)^6==2^2==4 (L+2)^12==4^2==16==5 [/CODE] This will work for all prime n==3 (mod 4), but is not proven that all composites will fail. Wagstaff are 3 (mod 4) To cover all n, I take minimal x>=0 such that jacobiSymbol(x^24,n)==1, and check: [CODE] (L+2)^(n+1)==5+2*x (mod n, L^2x*L+1) [/CODE] This is the basis of my [URL="http://www.mersenneforum.org/showpost.php?p=343535&postcount=73"]JavaScript program[/URL], which has the running time of 2 MillerRabin rounds. It is explained in [URL="http://www.mersenneforum.org/showpost.php?p=298027&postcount=44"]my preprint "Quadratic Composite Tests"[/URL] where I used [TEX]\lambda[/TEX] instead of "L". The general "minimal x" method is good for n < 10^13  I am currently testing n < 7*10^13. :smile: 
All times are UTC. The time now is 01:34. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2022, Jelsoft Enterprises Ltd.