mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Wagstaff PRP Search (https://www.mersenneforum.org/forumdisplay.php?f=102)
-   -   Searching for Wagstaff PRP (https://www.mersenneforum.org/showthread.php?t=13108)

 T.Rex 2010-02-20 14:12

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 [B]DUR[/B] gang :smile: (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 [URL="http://jpenne.free.fr/index2.html"]LLR tool built by Jean Penné[/URL] (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 :

[B][COLOR="Red"][SIZE="4"](2^4031399+1)/3 is Vrba-Reix PRP![/SIZE][/COLOR][/B]

This Wagstaff number has 1,213,572 digits and it is the 3rd biggest PRP ever found.
See: [URL="http://www.primenumbers.net/prptop/prptop.php?page=1#haut"]Lifchitz page[/URL] . (PRP submitted. Waiting for acceptation).

See [URL="http://www.research.att.com/~njas/sequences/A000978"]OEIS Wagstaff exponents page.[/URL]. (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 [URL="http://trex58.wordpress.com/math2matiques/"]Maths Page[/URL] .
People having ideas for proving the 3 conjectures are welcome !!
And [B]there is a 100€ reward ![/B] :smile:

I dedicate this Wagstaff PRP to my wife, [B]Catherine[/B], 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 [B]look for a proof for the 3 conjectures that my-self, Vrba and Gerbicz made[/B] 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%
[B][COLOR="Red"](2^4031399+1)/3 is PRP! [/COLOR][/B](56473.2345s+1.3909s)

 philmoore 2010-02-20 17:13

Congratulations! It sounds like your group was long overdue for a discovery, so I'm very happy a Wagstaff prp finally showed up!

 Raman 2010-02-20 18:44

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[sup]p[/sup]-1 are towards 8 digits for p, (2[sup]p[/sup]+1)/3 only 7 digits for p, and then finally those of form (10[sup]p[/sup]-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...

 T.Rex 2010-02-20 19:17

[QUOTE=Raman;206193]Good work indeed![/QUOTE]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?[/QUOTE]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[/QUOTE]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...[/QUOTE]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 2010-02-20 19:26

[QUOTE=philmoore;206184]Congratulations! It sounds like your group was long overdue for a discovery, so I'm very happy a Wagstaff prp finally showed up![/QUOTE]Thanks !

 Batalov 2010-02-20 19:42

Congratulations to the DUR team. Impressive!

[SIZE=1]There are [/SIZE][URL="http://www.primenumbers.net/prptop/searchform.php?form=%28n%5Em-1%29%2Fk"][SIZE=1]some repunits[/SIZE][/URL][SIZE=1] (and some [/SIZE][URL="http://www.primenumbers.net/prptop/searchform.php?form=%3F10%5E%3F-1%29%2F%3F"][SIZE=1]near-repunits[/SIZE][/URL][SIZE=1]) 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.[/SIZE]

 Raman 2010-02-20 19:58

[quote=Batalov;206201]
[SIZE=1]There are [/SIZE][URL="http://www.primenumbers.net/prptop/searchform.php?form=%28n%5Em-1%29%2Fk"][SIZE=1]some repunits[/SIZE][/URL][SIZE=1] (and some [/SIZE][URL="http://www.primenumbers.net/prptop/searchform.php?form=%3F10%5E%3F-1%29%2F%3F"][SIZE=1]near-repunits[/SIZE][/URL][SIZE=1]) 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.[/SIZE][/quote]

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 3[sup]p-1[/sup] = 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?

 T.Rex 2010-02-20 20:21

[QUOTE=Raman;206203]What is the difficulty in searching for Wagstaff, Repunit primes similar to those of Mersenne primes?[/QUOTE]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 3[sup]p-1[/sup] = 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?[/QUOTE]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 [URL="http://trex58.wordpress.com/math2matiques/"]these papers[/URL].
Tony

 axn 2010-02-21 01:04

[QUOTE=Batalov;206201]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[/QUOTE]

Doesn't the latest PFGW (using new gwnum library that sppeds up all non base-2 tests) accelerate repunit searches?

 axn 2010-02-21 03:15

[QUOTE=T.Rex;206205]I think this is what PFGW does. And PFGW is 5 times slower than Vrba-Reix.[/QUOTE]

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.

 CRGreathouse 2010-02-21 05:26

Congrats, Tony!

[QUOTE=T.Rex;206198]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]

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?

All times are UTC. The time now is 23:01.