P-1 factoring question

[siegert81]

From "The Math" section of GIMPS:

This method when adapted to Mersenne numbers is even more effective. Remember, that the factor q is of the form 2kp+1. It is easy to modify the P-1 method such that it will find the factor q whenever k is highly composite.

The P-1 method is quite simple. In stage 1 we pick a bound B1. P-1 factoring will find the factor q as long as all factors of k are less than B1 (k is called B1-smooth). We compute E – the product of all primes less than B1. Then we compute x = 3^E*2*P. Finally, we check the GCD (x-1, 2P-1) to see if a factor was found.

Does Prime95 only use one power of each prime less than B1 when computing E? Or does it use numerous powers of 2,3,5,7,11,13 and all other very small primes? After all, every 9th k value is divisible by 9, and if E only has one power of three, the GCD function will fail to produce all sorts of large factors of Mersenne numbers. If q=2*9*k*p+1, this implementation of P-1 would miss such a factor.

I would think E should be the product of all primes less than B1, all squares of primes less than the the square root of B1, all cubes of primes less than the cubic root of B1, etc.

Or am I way off here, missing something about the math?

When reading about P-1 factoring, K! was used instead which contains more than a sufficient number of powers of small primes.

If I am catching a missed opportunity here, then P-1 factoring for Mersenne numbers could be very substantially improved on using additional powers of the small primes. After all, numerous k values of real factors are divisible by 4, 8, 16, 32, 64, 128 or 9, 27, 81, or 25, 125, or 49, 121, 169, etc.

[cheesehead]

Originally Posted by siegert81

Does Prime95 only use one power of each prime less than B1 when computing E? Or does it use numerous powers of 2,3,5,7,11,13 and all other very small primes?

For each prime, it uses the highest power of that prime that is not larger than B1.

After all, every 9th k value is divisible by 9, and if E only has one power of three, the GCD function will fail to produce all sorts of large factors of Mersenne numbers. If q=2*9*k*p+1, this implementation of P-1 would miss such a factor.

But we don't see such misses. :-)

I would think E should be the product of all primes less than B1, all squares of primes less than the the square root of B1, all cubes of primes less than the cubic root of B1, etc.

If you said "less than or equal to" or "not larger than" instead of "less than", that would be correct.

Or am I way off here, missing something about the math?

No, you got it. The descriptions in "The Math" are not all perfect. :-(

You've found a documentation bug, or at least a nonclarity.

If I am catching a missed opportunity here, then P-1 factoring for Mersenne numbers

would have been missing many, many factors because of that. That number of P-1 misses would have been at least partially discovered by now after so many years, because of ECM or further TF.

But in fact, the few missed factors that are occasionally discovered have been missed because of other problems, not because of insufficient prime-powering in Prime95's implementation of P-1.

[LaurV]

Saying it differently, the described method guarantees that it searches all the "searching space" under B1, i.e. it will guarantee to find a factor q if q-1 is B1-power-smooth. Only talking about stage 1 here. Stage 2 is a different fish. Of course, you can use higher powers if you like, that would be a "shot in the dark", trying to find some factors "out of the searching space". It will be called an "extension" to the algorithm, and that is what Brent-Suyama extension is doing. You can do any type of "extensions" you like, but not all of them are worth a try, you can work in vain ages without finding a factor. Remark that you do not "extend" B1, by using larger powers, unless you do not add new primes to the exponent. Take a small example and try to do it practically.

[siegert81]

No, you got it. The descriptions in "The Math" are not all perfect. :-(

You've found a documentation bug, or at least a nonclarity.

Thank you. I would have been quite surprised if GIMPS had been using only one power of the small primes.