mersenneforum.org  

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

Reply
 
Thread Tools
Old 2018-07-25, 07:43   #23
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×3×227 Posts
Default

Quote:
Originally Posted by GP2 View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2018-07-25, 08:26   #24
GP2
 
GP2's Avatar
 
Sep 2003

2·1,289 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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?
GP2 is offline   Reply With Quote
Old 2018-07-25, 08:32   #25
axn
 
axn's Avatar
 
Jun 2003

121716 Posts
Default

Quote:
Originally Posted by GP2 View Post
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.
axn is offline   Reply With Quote
Old 2018-07-25, 10:40   #26
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

12428 Posts
Default

Quote:
Originally Posted by GP2 View Post
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
diep is offline   Reply With Quote
Old 2018-07-25, 10:55   #27
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

10101000102 Posts
Default

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
diep is offline   Reply With Quote
Old 2018-07-25, 11:07   #28
axn
 
axn's Avatar
 
Jun 2003

11×421 Posts
Default

Quote:
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?

Quote:
Originally Posted by diep View Post
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 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.
Quote:
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
Quote:
Originally Posted by diep View Post
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 View Post
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?
axn is offline   Reply With Quote
Old 2018-07-25, 11:08   #29
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×3×227 Posts
Default

Quote:
Originally Posted by diep View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2018-07-25, 11:14   #30
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

2×337 Posts
Default

>> 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.
diep is offline   Reply With Quote
Old 2018-07-25, 11:17   #31
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

2·337 Posts
Default

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.
diep is offline   Reply With Quote
Old 2018-07-25, 11:18   #32
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

2×337 Posts
Default

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.
diep is offline   Reply With Quote
Old 2018-07-25, 11:19   #33
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

2·337 Posts
Default

>> 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.
diep is offline   Reply With Quote
Reply

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 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

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.