mersenneforum.org  

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

Closed Thread
 
Thread Tools
Old 2018-08-01, 20:10   #56
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

72×31 Posts
Default

Quote:
Originally Posted by diep View Post
Yet in our lifetime we do not yet know how far we will be able to test to find sufficient datapoints there.
Not going into this deep numerology staff, but we have already a lot of results, if I understand correctly the search for Wagstaff prime is complete up to p=15e6, the Mersenne prime search also reached this. We have 43 Wagtsaff prime, and **only** 39 Mersenne prime up to p=15e6, so what would you search? My 2 cents: probably the density is the same (a similar heuristic what used for Mersenne could work here), ofcourse the big drawback for Wagstaff that we have no (known) fast primality test.
R. Gerbicz is offline  
Old 2018-08-01, 20:15   #57
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

11000011012 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Not going into this deep numerology staff, but we have already a lot of results, if I understand correctly the search for Wagstaff prime is complete up to p=15e6, the Mersenne prime search also reached this. We have 43 Wagtsaff prime, and **only** 39 Mersenne prime up to p=15e6, so what would you search? My 2 cents: probably the density is the same (a similar heuristic what used for Mersenne could work here), ofcourse the big drawback for Wagstaff that we have no (known) fast primality test.
The first few n's, see it like Wagstaff is a propellor airplane. It had some advantages, was easier to build, yet Mersenne is a fighter jet. Lots of problems to get started and some hiccups, yet after it finally took off at the million bits area, it produces very systematic primes now.

Distance between each wagstaff and the next one simply is factor 3 nearly.
diep is offline  
Old 2018-08-01, 20:23   #58
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5EF16 Posts
Default

Quote:
Originally Posted by diep View Post
Distance between each wagstaff and the next one simply is factor 3 nearly.
Yeah, like at 13347311, 13372531.
R. Gerbicz is offline  
Old 2018-08-01, 20:26   #59
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

11×71 Posts
Default

You ignore what i wrote.

To find the NEXT one, even if 3 prp's lurk nearby, you want to know the DISTANCE you need to search to find 'em.

3 x 13M = 40M
diep is offline  
Old 2018-08-02, 01:04   #60
GP2
 
GP2's Avatar
 
Sep 2003

5×11×47 Posts
Default

Quote:
Originally Posted by diep View Post
most recent history:
13 / 4 = factor 3.25 distance
4 / 1 = factor 4.0 distance
981k / 374321 = factor 2.6 distance
If Wagstaff primes are distributed like Mersenne primes (is it true?), then we would expect an average ratio of 1.47576 between exponents of successive primes.

For Mersennes, the highest ratios are:

Code:
521 / 127 = 4.10
756839 / 216091 = 3.50
with everything else at 2.31 or lower.


For Wagstaffs, the highest ratios are:

Code:
1709 / 701 = 2.44
42737 / 14479 = 2.95
986191 / 374321 = 2.63
4031399 / 986191 = 4.09
13347311 / 4031399 = 3.31
with everything else at 2.02 or lower.


Those three very high ratios in a row do seem anomalous. But can we be certain they are real?

Maybe I'm mistaken, but I think the large rangers were tested with programs that assumed the Vrba-Reix conjecture is correct.

If there are counterexamples to this conjecture, then maybe some Wagstaff primes were missed?


Quote:
Originally Posted by R. Gerbicz View Post
Why not use my own error checking on these numbers? Even a single run is much stronger than your double or even triple/quadruple check if you compare only RES64. The same is true for Mersenne numbers.
The previous testing was mostly done in 2013 and earlier.

Today mprime can do PRP testing with Gerbicz error checking, and it does not depend on Vrba-Reix being true. And we have faster CPUs with more cores, and faster GPUs that can find more factors.

I am seriously considering throwing some resources into Wagstaff testing old ranges using mprime. I don't know how far it would go, but the goal would be to publish the PRP residues and a consolidated list of new factors and old factors from multiple available sources, as a permanent verifiable record.

Sadly, there don't seem to be too many published results from the 2013 efforts, other than the primes that were found. Some lists of factors were published, but others are harder to track down and might even be lost.

Ideally, the PRP residues should be recorded with a lot more than 64 bits. If the only goal is double-check verifiability, then 64 bits is plenty; however, larger residues might let us do quick PRP-cofactor checking for newly discovered factors. (I presume the analysis at the linked page for Mersennes applies similarly for Wagstaffs, or is "inv" different?)

So, at least 512 bits, or with an eye to future decades, who knows, maybe even 2048. Storage is very cheap.

I'm not aware of any undoc.txt setting for mprime that would output residues larger than 64 bits, but hopefully it would be straightforward to add.
GP2 is offline  
Old 2018-08-02, 10:10   #61
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

30D16 Posts
Default

Yeah you are mistaken.

Things at million bit size really works different than at a handful of bits.

If you want to search in the dozens of millions bit range and then basing your expectation to find something upon a handful of bits for that, makes no sense at all.

Last fiddled with by diep on 2018-08-02 at 10:19
diep is offline  
Old 2018-08-02, 11:22   #62
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×2,417 Posts
Default

Quote:
Originally Posted by diep View Post
Yeah you are mistaken.

Things at million bit size really works different than at a handful of bits.

If you want to search in the dozens of millions bit range and then basing your expectation to find something upon a handful of bits for that, makes no sense at all.
You consider an LL test passed or not by checking a single bit: true or false.

If a Law works in math, the number of involved bits does not matter.
ET_ is offline  
Old 2018-08-02, 11:57   #63
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

11×71 Posts
Default

it's about the short term expectation how much of a computational work you need to throw in to find the next gem.

Whether you find 1 or a million doesn't matter - you first have to do that huge computational effort to find at least 1.
So the way how the PRP's have been spread also matter quite a lot.

Last fiddled with by diep on 2018-08-02 at 12:01
diep is offline  
Old 2018-08-02, 14:00   #64
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×33×73 Posts
Default

If one was searching for Wagstaff co-factors then they can be PRP'ed over 2^p+1 before a final modular reduction. I guess Prime95 does this.

Last fiddled with by paulunderwood on 2018-08-02 at 14:05
paulunderwood is online now  
Old 2018-08-02, 14:33   #65
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

So in summary:

diep: We should ignore everything but the big numbers, numbers at millions of bits aren't like numbers with just a few bits. The big Wagstaff exponents are spread very thin.

GP2: You're throwing out most of the data, if you look at the broader picture you see the Wagstaff exponents aren't that thin. Also, the higher ranges might have missed some primes because searches relied on a conjecture.
CRGreathouse is offline  
Old 2018-08-02, 15:05   #66
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

11·71 Posts
Default

You mean missed above 10M until 13M?

Possible. Until 10M you won't find anything new.

A 3-PRP will find anything of course there for both mersenne and wagstaff.
Doing a 27-PRP test which the conjecture uses is pretty obvious the same thing like doing a 3-PRP at least. So it won't miss anything. Whether it is a method to prove them prime - that i leave up to the theoretists with enough time :)
diep is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Testing Mersenne Primes with Elliptic Curves a nicol Math 3 2017-11-15 20:23
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
Statistical odds for prime in Wagstaff vs Mersenne diep Math 27 2010-01-13 20:18
Speed of P-1 testing vs. Trial Factoring testing eepiccolo Math 6 2006-03-28 20:53

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


Mon Dec 6 20:23:06 UTC 2021 up 136 days, 14:52, 0 users, load averages: 1.97, 1.77, 1.83

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