mersenneforum.org Status of Wagstaff testing? and testing Mersenne primes for Wagstaff-ness
 Register FAQ Search Today's Posts Mark Forums Read

2018-07-25, 07:43   #23
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×3×227 Posts

Quote:
 Originally Posted by GP2 Wagstaff numbers ( 2p + 1) / 3 for odd p ) appear to share with Mersenne numbers ( 2p − 1 ) the characteristic that all their factors are of the form 2kp + 1 for some k.
Elementary school stuff. Maybe nowadays you can learn this only in university.

2018-07-25, 08:26   #24
GP2

Sep 2003

2·1,289 Posts

Quote:
 Originally Posted by R. Gerbicz Elementary school stuff. Maybe nowadays you can learn this only in university.
Code:
#! /usr/bin/python3
import fileinput
with fileinput.input() as f:
for line in f:
p, f = line.strip().split(",", maxsplit=2)
p = int(p)
f = int(f)
if (f - 1) % (2*p) != 0:
print ("UNEXPECTED FORM: ", p, f)
It takes a little less time to dash off a few lines of Python script to run over the 1.75-million-line factors file than to look up the proof for Mersennes and then try to see how −1 instead of 1 might affect it. I didn't study math formally and that makes everything slower to figure out, so I take the lazy empirical way... math as an experimental science.

What can we say for the general case of k × bn + c ? Which values for the constants k, b, c let us do P−1 testing more effectively in the source code of mprime/Prime95?

2018-07-25, 08:32   #25
axn

Jun 2003

121716 Posts

Quote:
 Originally Posted by GP2 However, I was digging up old Wagstaff-related threads, and came up with this one from 2011. It seems that in the source code, the 2 * p efficiency boost for P−1 testing is only applied to Mersenne numbers. In other words, only for k*b^n+c where k = 1, b = 2 and c = −1.
To be clear, what is missing is the probability calculation, and hence the bound selection logic. The actual P-1 will throw in the p for free. Because of the former, it will pick much lower (and suboptimal) bounds, if asked to do so. However, if you give the bounds (after calculating the same for equivalent mersenne), it would indeed be efficient.

2018-07-25, 10:40   #26
diep

Sep 2006
The Netherlands

12428 Posts

Quote:
 Originally Posted by GP2 It doesn't make sense that P−1 testing should be ineffective for Wagstaff.
Oh it does compared to the alternatives.

Let's first focus upon the reality. that's that in the GIMPS project most people wanted a chance to find a prime. So they wanted to TEST rather than TF and initially there wasn't a gpgpu version of TF. They simply didn't do a very deep TF initially for Mersenne. It was just so so.

Additionally Wagstaff TF's much better than Mersenne. so you keep left with a far smaller percentage of numbers to test for PRP than to LL.

TF simply is more effective in that sense for Wagstaff.

So there is a number of things that make this plausible:

a) there is a smaller percentage of numbers left with wagstaff after TF than with mersenne.
b) nowadays the TF is far far far deeper than years ago with Mersenne
c) Mersenne is at dozens of millions of bits, Wagstaff still is at 10+ million bits.
d) we divide by 3 so it's not a +1 number of bits. It's a -1 number of bits.

It's especially B. the mersenne project has been pretty lazy in that respect. Everyone wanted a chance to find a prime. So they started testing long before a good TF had been done.

Last fiddled with by diep on 2018-07-25 at 10:44

 2018-07-25, 10:55 #27 diep     Sep 2006 The Netherlands 10101000102 Posts Let me focus upon argument D as this is the thing most researchers seem to forget. x = 2^p + 1; We first divide a number length len = prime p number of bits We divide it by 3. If we take p = 5 2^5 + 1 = 33 = 0b100001 bits = 6 bits we divide it by 3 ==> 33 / 3 = 11 = 0b1011 = 4 bits So we want a prime of 4 bits which is p-1 bits. That's a lot of constraints we want to find a prime. Last fiddled with by diep on 2018-07-25 at 10:57
2018-07-25, 11:07   #28
axn

Jun 2003

11×421 Posts

Quote:
 Originally Posted by diep Oh it does compared to the alternatives.
What alternative? P-1 is a complementary method to TF, not an alternative. And ECM is not cost competitive with P-1. What other alternative is there?

Quote:
 Originally Posted by diep Let's first focus upon the reality. that's that in the GIMPS project most people wanted a chance to find a prime. So they wanted to TEST rather than TF and initially there wasn't a gpgpu version of TF. They simply didn't do a very deep TF initially for Mersenne. It was just so so.
You're just conflating many things. I'm sure some people at some time would have jumped the gun and LL tested under-TF'ed, but for the most part, GIMPS has always tried to do optimal TF (and P-1) before LL-test. The optimal level for CPU-based TF is different from optimal level of GPU-based TF. If you don't understand why that is so, you have a problem

Quote:
 Originally Posted by diep a) there is a smaller percentage of numbers left with wagstaff after TF than with mersenne.
I don't know why this should be so... but I'll take your word for it. However this has no relevance as to whether doing P-1 after TF is worthwhile.
Quote:
 Originally Posted by diep b) nowadays the TF is far far far deeper than years ago with Mersenne
Due to GPU-TF. If Wagstaff's have also been similarly deeply TF'ed with GPUs, then the P-1 breakeven point would shift
Quote:
 Originally Posted by diep c) Mersenne is at dozens of millions of bits, Wagstaff still is at 10+ million bits.
This is a valid point. At different sizes and different TF levels, the P-1 breakeven point changes. But you have to do the actual probability calculation to see if it makes sense. Gut feelings don't cut it.
Quote:
 Originally Posted by diep d) we divide by 3 so it's not a +1 number of bits. It's a -1 number of bits.
Not sure I understand. What do you mean by this?

2018-07-25, 11:08   #29
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×3×227 Posts

Quote:
 Originally Posted by diep d) we divide by 3 so it's not a +1 number of bits. It's a -1 number of bits.
Not likely, because when you'd divide by 3 you'd already know 2^p+1, right?

Last fiddled with by R. Gerbicz on 2018-07-25 at 11:12

 2018-07-25, 11:14 #30 diep     Sep 2006 The Netherlands 2×337 Posts >> Originally Posted by diep View Post >>a) there is a smaller percentage of numbers left with wagstaff after TF than with >>mersenne. > I don't know why this should be so... but I'll take your word for it. However this has > no relevance as to whether doing P-1 after TF is worthwhile. Sir, if you do not understand this one, i propose that you first study this one in depth first before claiming it doesn't matter.
 2018-07-25, 11:17 #31 diep     Sep 2006 The Netherlands 2·337 Posts Originally Posted by diep View Post >> b) nowadays the TF is far far far deeper than years ago with Mersenne > Due to GPU-TF. If Wagstaff's have also been similarly deeply TF'ed with GPUs, then the P-1 breakeven point would shift It is a very silly assumption to assume you will not be using some massive gpu's to TF. The amount of system time to factor with a silly algorithm like P-1 provable is nonsense except if you can do that on hardware that wouldn't be used for PRP-testing otherwise. GPU's are so much faster than the hardware most have to do PRP-testing, it's just not even funny to compare the 2.
 2018-07-25, 11:18 #32 diep     Sep 2006 The Netherlands 2×337 Posts Originally Posted by diep View Post >> Oh it does compared to the alternatives. > What alternative? P-1 is a complementary method to TF, not an alternative. And ECM is not cost competitive with P-1. What other alternative is there? You get what you pay for.
 2018-07-25, 11:19 #33 diep     Sep 2006 The Netherlands 2·337 Posts >> d) we divide by 3 so it's not a +1 number of bits. It's a -1 number of bits. > Not sure I understand. What do you mean by this? Wagstaff is a much harder beast than Mersenne.

 Similar Threads Thread Thread Starter Forum Replies Last Post a nicol Math 3 2017-11-15 20:23 ryanp Wagstaff PRP Search 26 2013-10-18 01:33 Batalov GMP-ECM 9 2012-08-24 10:26 diep Math 27 2010-01-13 20:18 eepiccolo Math 6 2006-03-28 20:53

All times are UTC. The time now is 22:36.

Fri Jul 3 22:36:42 UTC 2020 up 100 days, 20:09, 1 user, load averages: 0.86, 1.27, 1.34