Status of Wagstaff testing? and testing Mersenne primes for Wagstaff-ness

[R. Gerbicz]

Originally Posted by GP2

Wagstaff numbers ( 2^p + 1) / 3 for odd p ) appear to share with Mersenne numbers ( 2^p − 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.

[GP2]

Originally Posted by R. Gerbicz

Elementary school stuff. Maybe nowadays you can learn this only in university.

#! /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 × bⁿ + c ? Which values for the constants k, b, c let us do P−1 testing more effectively in the source code of mprime/Prime95?

[axn]

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.

[diep]

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.

[diep]

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.

[axn]

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?

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

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.

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

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.

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?

[R. Gerbicz]

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?

[diep]

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

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]

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]

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