mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Wagstaff PRP Search

Reply
 
Thread Tools
Old 2010-02-20, 14:12   #1
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default 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 Vrba-Reix 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 non-prime 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 Vrba-Reix 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^2-2 of the LLT (Lucas-Lehmer 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 Vrba-Reix 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 Vrba-Reix 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 Vrba-Test used by LLR 3.8.0 was imagined after my research about Mersennes and LLT (Lucas-Lehmer 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 (Lucas-Lehmer-Riesel) 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 Vrba-Reix 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 my-self, 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 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base
2
Running N-1 test using base
5
Calling Brillhart-Lehmer-Selfridge with factored part 0.00%
(2^4031399+1)/3 is PRP! (56473.2345s+1.3909s)
T.Rex is offline   Reply With Quote
Old 2010-02-20, 17:13   #2
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default

Congratulations! It sounds like your group was long overdue for a discovery, so I'm very happy a Wagstaff prp finally showed up!
philmoore is offline   Reply With Quote
Old 2010-02-20, 18:44   #3
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

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 2p-1 are towards 8 digits for p, (2p+1)/3 only 7 digits for p, and then finally those of form (10p-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...
Raman is offline   Reply With Quote
Old 2010-02-20, 19:17   #4
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

11100011112 Posts
Default

Quote:
Originally Posted by Raman View Post
Good work indeed!
Thanks.
Quote:
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?
I think it's because there is no primality test for these numbers as there are for Mersennes.

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:
In my opinion, we seem to have already enough of Mersenne primes
No, we need more ! But that would be nice to be able to find big Wagstaff primes too !

Quote:
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...
Read the papers I've put on my Math site. If you have Number Theory skills, you could build a proof ! And then, you'll be famous, because that would be the first fast primality test for a number that is not of the N-1 or N+1 form, where N can be easily factored.

Tony
T.Rex is offline   Reply With Quote
Old 2010-02-20, 19:26   #5
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

911 Posts
Default

Quote:
Originally Posted by philmoore View Post
Congratulations! It sounds like your group was long overdue for a discovery, so I'm very happy a Wagstaff prp finally showed up!
Thanks !
T.Rex is offline   Reply With Quote
Old 2010-02-20, 19:42   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·17·89 Posts
Default

Congratulations to the DUR team. Impressive!

[while I was reading Tony already answered 'why'.]
There are some repunits (and some near-repunits) to be found in the PRP table. But because there's no Vrba-Reix 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.
Batalov is offline   Reply With Quote
Old 2010-02-20, 19:58   #7
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

Quote:
Originally Posted by Batalov View Post
[while I was reading Tony already answered 'why'.]
There are some repunits (and some near-repunits) to be found in the PRP table. But because there's no Vrba-Reix 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.
List of Mersenne Primes:
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 3p-1 = 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?
Raman is offline   Reply With Quote
Old 2010-02-20, 20:21   #8
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

38F16 Posts
Default

Quote:
Originally Posted by Raman View Post
What is the difficulty in searching for Wagstaff, Repunit primes similar to those of Mersenne primes?
We have a fast primality proof for Mersennes. We do not have for Wagstaff. Proving that (2^42737+1)/3 is a prime took a month or more by François Morain with Fast ECPP, though, with Vrba-Reix test it takes less than 1 hour to prove it is a PRP.
Quote:
A Fermat's Little Theorem Test will make us suspect the primality of Wagstaff, Repunit primes, say for base = 3, that is enough.
If 3p-1 = 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?
I think this is what PFGW does. And PFGW is 5 times slower than Vrba-Reix. As for Mersennes, the method used for proving that a Wagstaff is PRP makes use of the LLT method. Same cost. But not the same effect yet... Read these papers.
Tony
T.Rex is offline   Reply With Quote
Old 2010-02-21, 01:04   #9
axn
 
axn's Avatar
 
Jun 2003

2·32·7·37 Posts
Default

Quote:
Originally Posted by Batalov View Post
But because there's no Vrba-Reix 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
Doesn't the latest PFGW (using new gwnum library that sppeds up all non base-2 tests) accelerate repunit searches?
axn is online now   Reply With Quote
Old 2010-02-21, 03:15   #10
axn
 
axn's Avatar
 
Jun 2003

2×32×7×37 Posts
Default

Quote:
Originally Posted by T.Rex View Post
I think this is what PFGW does. And PFGW is 5 times slower than Vrba-Reix.
No it isn't. PFGW did a N-1 test. It is actually a lot stronger test than Fermat test. Unfortunately, since the factored part of N-1 didn't amount to 33%, it doesn't constitute a primality proof, so it still declares it a PRP only.

A standard Fermat test will be only slightly slower (maybe 5%?) than a V-R test.
axn is online now   Reply With Quote
Old 2010-02-21, 05:26   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×3×977 Posts
Default

Congrats, Tony!

Quote:
Originally Posted by T.Rex View Post
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 !
My apologies for being 'out of the loop'. But what is known about these so-called Vrba-Reix prps? All Wagstaff primes are VRprps, but is it known that composite VRprps are asymptotically rare?
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New Wagstaff PRP exponents ryanp Wagstaff PRP Search 26 2013-10-18 01:33
Hot tuna! -- a p75 and a p79 by Sam Wagstaff! Batalov GMP-ECM 9 2012-08-24 10:26
Wagstaff Conjecture davieddy Miscellaneous Math 209 2011-01-23 23:50
Best settings to factor Wagstaff p = (2^n +1) / 1 diep GMP-ECM 10 2010-07-26 21:33
30th Wagstaff prime T.Rex Math 0 2007-09-04 07:10

All times are UTC. The time now is 08:13.

Wed Aug 5 08:13:10 UTC 2020 up 19 days, 3:59, 1 user, load averages: 1.52, 1.48, 1.37

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.