20100220, 14:12  #1 
Feb 2004
France
2×3^{3}×17 Posts 
Searching for Wagstaff PRP
Hi,
I searched in the Mersenne forum where to post this news... Since there are pages dedicated for Primes and Factorizations but not for PRPs, I decided to talk there. This finding is closely related to the Mersenne numbers and to the GIMPS, since the LLR tool that has been used to test the candidates makes use of the gwnum library, since the Wagstaff numbers are very close to Mersenne numbers, and since the VrbaReix method that has been used is very close to the LLT method used by the GIMPS project. This PRP has more than 1,2 Millions of digits. It is the 3rd ever known biggest PRP number. A PRP is a PRobable Prime. That often means to say that such a number has a property that prime numbers of a specific form have, though there is no proof that nonprime numbers of this form cannot also have this property. That means that a number that does not have such a property cannot be a prime. A Wagstaff number is a number of the form: (2^q+1)/3, where q is a prime. Only 30 Wagstaff primes are known. And only 10 Wagstaff PRP were known. The method used to search this Wagstaff PRP is the VrbaReix PRP test, imagined and proved by Anton Vrba, based on a preliminary work I did about Mersenne numbers and about the use of the Cycles of the DiGraph under x^22 of the LLT (LucasLehmer Test) as a primality test for Mersenne numbers. As a member of the DUR gang (where DUR means: Diepeveen, Underwood, and Reix), which is a project initiated (about 18 months ago) and managed by Vincent Diepeveen for finding new Wagstaff PRPs by means of the LLR tool built by Jean Penné (based on the gwnum library by George Woltman) who implemented the VrbaReix PRP test, I've found a new and big Wagstaff PRP. Previous Wagstaff PRP was found by Vincent Diepeveen : (2^986191+1)/3 in June 2008. This Thursday 18th of February 2010, after testing about 43000 Wagstaff candidates during about 16 months, I've got the following message by Jean Penné's fresh version 3.8.0 of LLR : (2^4031399+1)/3 is VrbaReix PRP! This Wagstaff number has 1,213,572 digits and it is the 3rd biggest PRP ever found. See: Lifchitz page . (PRP submitted. Waiting for acceptation). See OEIS Wagstaff exponents page.. (PRP submitted. Waiting for acceptation). I've done a second verification on a Nehalem core, still with LLR 3.8.0 : OK after less than 3 hours. I've also ran the PFGW tool (with t option) on Nehalem, which said: (2^4031399+1)/3 is PRP! after about 15 hours. See below for details. I guess that another independent verification is required before this PRP is accepted. However, testing with two different methods is already very positive. I'm very happy ! I thank a lot Vincent for proposing me to take part in this project. He managed the exponents ranges and he sieved all the exponents I've tested. He and Paul Underwood tested many exponents too. But I think I deserved to find this PRP since I've tested a very big part of all candidate exponents, and also because the VrbaTest used by LLR 3.8.0 was imagined after my research about Mersennes and LLT (LucasLehmer Test) properties. I also thank a lot Jean Penné, who decided to implement the test imagined by Anton Vrba, and who spent hours to upgrade the LLR (LucasLehmerRiesel) tool so that the 3.8.0 version is much more reliable than previous 3.7.2 version, thanks to new gwnum library, but also due to some very useful checking mechanisms he put at work (random shift at start). For those interested by the theory behind the VrbaReix test, have a look at my Maths Page . People having ideas for proving the 3 conjectures are welcome !! And there is a 100€ reward ! I dedicate this Wagstaff PRP to my wife, Catherine, who died the 29th of October, 2006, and who never understood why I was spending so much time about these crazy and unuseful Number Theory mathematics. Maybe I should have spent more time with her than I spent as an amateur with Mersenne and LLT theory... Maybe women are wiser than men... All this long email is aimed to push Number Theory guys to look for a proof for the 3 conjectures that myself, Vrba and Gerbicz made about 2 years ago. Regards, Tony Reix $ ./pfgw t q"(2^4031399+1)/3" PFGW Version 20091218.x86_Dev (Beta 'caveat utilitor') [GWNUM 25.13] Primality testing (2^4031399+1)/3 [N1, BrillhartLehmerSelfridge] Running N1 test using base 2 Running N1 test using base 5 Calling BrillhartLehmerSelfridge with factored part 0.00% (2^4031399+1)/3 is PRP! (56473.2345s+1.3909s) 
20100220, 17:13  #2 
"Phil"
Sep 2002
Tracktown, U.S.A.
3×373 Posts 
Congratulations! It sounds like your group was long overdue for a discovery, so I'm very happy a Wagstaff prp finally showed up!

20100220, 18:44  #3 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
4E9_{16} Posts 
Good work indeed!
Why can't we have projects to find out more PRPs/primes for the Wagstaff and then those Repunit prime candidates, similar to the GIMPS project? Numbers of form 2^{p}1 are towards 8 digits for p, (2^{p}+1)/3 only 7 digits for p, and then finally those of form (10^{p}1)/9 only hardly 6 digits for values of p? I think that we should concentrate upon these numbers as well. In my opinion, we seem to have already enough of Mersenne primes, but the priority of these new projects may be lesser than that of GIMPS. Because mainly of the fact that every new Mersenne prime that is being discovered gives out with a new perfect number as well! Are there already any projects that are going on for those aiming upon the new Wagstaff and then Repunit prime discoveries? Or are there any prime confirming algorithms for those Wagstaff, Repunit numbers? We have already that Lucas Lehmer Test, Pépin's Test, Proth's Theorem, Lucas Lehmer Riesel tests for those Mersenne, Fermat, Riesel, Sierpinski numbers respectively... 
20100220, 19:17  #4  
Feb 2004
France
918_{10} Posts 
Thanks.
Quote:
Finding a big Wagstaff PRP is a way for me to make focus on these numbers and on the method used to find it. There are plenty of Wagstaff primes, more than Mersennes. The problem is that we lack a proof for Vrba conjecture. We need a proof ! Also, a PRP is less impressive than a prime... I'm sure that the Wagstaff PRP I found is a prime. However, without a proof, it is only... a PRP. People have a preference for primes, for sure ! Quote:
Quote:
Tony 

20100220, 19:26  #5 
Feb 2004
France
2×3^{3}×17 Posts 

20100220, 19:42  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×5^{2}×127 Posts 
Congratulations to the DUR team. Impressive!
[while I was reading Tony already answered 'why'.] There are some repunits (and some nearrepunits) to be found in the PRP table. But because there's no VrbaReix accelerator/conjecture (3hr tests instead of 15hr, right?), they take years to search and ages to find. And the limits where people stop are much lower. 
20100220, 19:58  #7  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3×419 Posts 
Quote:
2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423 9689 9941 11213 19937 21701 23209 44497 86243 110503 132049 216091 756839 859433 1257787 1398269 2976221 3021377 6972593 13466917 20996011 24036583 25964951 30402457 32582657 37156667 42643801 43112609 List of Wagstaff Primes: 2 3 5 7 11 13 17 19 23 31 43 61 79 101 127 167 191 199 313 347 701 1709 2617 3539 5807 10501 10691 11279 12391 14479 42737 83339 95369 117239 127031 138937 141079 267017 269987 374321 986191 4031399 List of Repunit Primes: 2 19 23 317 1031 49081 86453 109297 270343 What is the difficulty in searching for Wagstaff, Repunit primes similar to those of Mersenne primes? A Fermat's Little Theorem Test will make us suspect the primality of Wagstaff, Repunit primes, say for base = 3, that is enough. If 3^{p1} = 1 (mod p), then p is probably prime, where p is a Wagstaff or Repunit prime itself. Can't we do these modular computations effectively in logarithmic time only, similar to the Lucas Lehmer Test? Modular exponentiation allows for modular squaring for these modular computations, thus can't we make use of Fast Fourier Transform or atleast even the Discrete Weighted Transform in order to square these numbers modulo p quickly and efficiently, then? 

20100220, 20:21  #8  
Feb 2004
France
396_{16} Posts 
Quote:
Quote:
Tony 

20100221, 01:04  #9 
Jun 2003
2^{10}×5 Posts 
Doesn't the latest PFGW (using new gwnum library that sppeds up all non base2 tests) accelerate repunit searches?

20100221, 03:15  #10  
Jun 2003
2^{10}·5 Posts 
Quote:
A standard Fermat test will be only slightly slower (maybe 5%?) than a VR test. 

20100221, 05:26  #11  
Aug 2006
3·1,993 Posts 
Congrats, Tony!
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New Wagstaff PRP exponents  ryanp  Wagstaff PRP Search  26  20131018 01:33 
Hot tuna!  a p75 and a p79 by Sam Wagstaff!  Batalov  GMPECM  9  20120824 10:26 
Wagstaff Conjecture  davieddy  Miscellaneous Math  209  20110123 23:50 
Best settings to factor Wagstaff p = (2^n +1) / 1  diep  GMPECM  10  20100726 21:33 
30th Wagstaff prime  T.Rex  Math  0  20070904 07:10 