Understanding P+1

[James Heinrich]

I'm passingly familiar with P-1, at least as far as how k and bounds determine what factors can be found with it. I'm unfamiliar with P+1 other than I've heard the term.
Can someone, in simple terms, explain to me the similar rules for how P+1 works?

[ATH]

From a practical standpoint it is almost the same as P-1. P+1 will find a factor P if all the factors of P+1 are below the B1 bound, except 1 factor can be between B1 and B2.

The main difference is that only half the seeds "x0" works for P+1, so it will only find factors half the time even though factors of P+1 are within B1 and B2. That is why it is useful to run 2-3 P+1 tests with the same B1 and B2, which is useless for P-1.
Generally P+1 tests are slower than P-1 tests with the same B1 and B2, I do not remember by how much, it was a long time since I ran either.


From GMP-ECM "Readme":

The P+1 method works well when the input number has a prime factor P such
that P+1 is "smooth". For P=4190453151940208656715582382315221647, we have
P+1 = 2^4 * 283 * 2423 * 21881 * 39839 * 1414261 * 2337233 * 132554351, so
this factor will be found as long as B1 >= 2337233 and B2 >= 132554351:

$ echo 4190453151940208656715582382315221647 | ./ecm -pp1 -x0 7 2337233 132554351
GMP-ECM ... [powered by GMP ...] [P+1]
Input number is 4190453151940208656715582382315221647 (37 digits)
Using B1=2337233, B2=2324738-343958122, x0=7
Step 1 took 750ms
Step 2 took 120ms
********** Factor found in step 2: 4190453151940208656715582382315221647
Found input number N

However not all seeds will succeed: only half of the seeds 'x0' work for P+1
(namely those where the Jacobi symbol of x0^2-4 and P is -1.) Unfortunately,
since P is usually not known in advance, there is no way to ensure that this
holds. However, if the seed is chosen randomly, there is a probability of
about 1/2 that it will give a Jacobi symbol of -1 (i.e., the factor P will
be found if P+1 is smooth enough). A rule of thumb is to run 3 times P+1
with different random seeds. The seeds 2/7 and 6/5 have a slightly higher
chance of success than average as they lead to a group order divisible by
6 or 4, respectively. When factoring Fibonacci numbers F_n or Lucas
numbers L_n, using the seed 23/11 ensures that the group order is
divisible by 2n, making other P+1 (and probably P-1) work unnecessary.

[James Heinrich]

Originally Posted by ATH

From GMP-ECM "Readme":

Helpful, thank you.

[ATH]

Because the need to run 2-3 P+1 tests at each B1 and the tests taking longer, generally people do not run as much P+1 as P-1 before moving on to ECM.

[Prime95]

P+1 stage 1 would be a little less than twice as slow as P-1 stage 1.
P+1 stage 2 would be a little faster than P-1 stage 2.

If prime95 supported P+1 it might produce output like this for a 2/7 start:

P+1 found a factor in stage #2, B1=704000, B2=70400000.
M4933 has a factor: 1462068605459232546304443160060228598409160926819654103423529 (P+1, B1=704000, B2=70400000)

and this for a 6/5 start:

P+1 found a factor in stage #2, B1=704001, B2=70400100.
M4933 has a factor: 16237378233362413121723422738420712221935933479 (P+1, B1=704001, B2=70400100)

[James Heinrich]

I understand how to get from a P-1 factor to the required bounds to guaranteed find said factor (and thereby the pretty graph on my exponent pages).

I don't understand the equivalent for how to get something analogous for P+1 to determine what bounds would be required for that factor to have a chance to be found (given an auspicious seed).

1462068605459232546304443160060228598409160926819654103423529 + 1 = 
2 * 3^2 * 5 * 7 * 11 * 23 * 5737 * 13925306493324727 * 114819874685022095060848628626224373

Originally Posted by Prime95

If prime95 supported P+1 it might produce output like this for a 2/7 start:

Presumably the seed choice might be interesting (is it?). Is it encoded somewhere in the output I didn't see, or perhaps it's determinable from the factor found?

[Prime95]

Caveat: I'm not a P+1 expert.

Originally Posted by James Heinrich

Presumably the seed choice might be interesting (is it?). Is it encoded somewhere in the output I didn't see, or perhaps it's determinable from the factor found?

When we do P-1 on Mersenne numbers factors are of the form f=2kp+1, thus we find a factor f when k=(f-1)/(2p) is B1/B2-smooth.

With P+1, factors are of the form f=2k-1. We find a factor f when k=(f+1)/2 is B1/B2-smooth but only 50% of the time.

The P+1 2/7 seed is special, we find a factor f when k=(f+1)/6 is B1/B2-smooth but only 50% of the time.

The P+1 6/5 seed is also special, we find a factor f when k=(f+1)/4 is B1/B2-smooth but only 50% of the time.

The P+1 experts can correct any mistakes I've made above.


Were prime95 to support P+1 it would output the seed somewhere, likely the JSON text.

[Prime95]

Originally Posted by James Heinrich

1462068605459232546304443160060228598409160926819654103423529 + 1 = 
2 * 3^2 * 5 * 7 * 11 * 23 * 5737 * 13925306493324727 * 114819874685022095060848628626224373

Lookup M4933 at mersenne.ca to see how 14620... factors.

To make understanding the P+1 algorithm even more complicated, the 50% of the time the algorithm misses P+1 factors, the algorithm was looking for P-1 factors. That is, the algorithm is part P+1 and part P-1.

[axn]

Originally Posted by James Heinrich

I understand how to get from a P-1 factor to the required bounds to guaranteed find said factor (and thereby the pretty graph on my exponent pages).

I don't understand the equivalent for how to get something analogous for P+1 to determine what bounds would be required for that factor to have a chance to be found (given an auspicious seed).

Exactly the same. Just, instead of factoring f-1 (and ignoring the forced "2p"), you factor f+1. B1 is second-largest factor, B2 is largest.

[kriesel]

Interesting stuff.
How useful would P+1 be, for wavefront Mersenne exponents?
I had thought the applicable factoring methods were already fully exploited by GIMPS.

How applicable is Mihai's method of saving some powers of 3 produced from PRP iteration computations, in the parallel approach of PRP and P-1 stage 1, for a possible parallel P+1 stage 1 (also)?
Is one attempt at P+1 with seed 3 or 9 fast enough to be worthwhile? (Does seed 3 even work for Mersennes?)
https://en.wikipedia.org/wiki/Willia...2B_1_algorithm gives an example using seed 9 and seed 5.
Seems to me if we were going to attempt both P+1 and P-1, P+1 would go first, and then a determination whether it was in effect a slow P-1, since it seems pointless to do P-1 slow and then again fast on the same bounds and seed.

Is there anything to be gained by the generalization to cyclotomic polynomials?
https://www.ams.org/journals/mcom/19...-0947467-1.pdf
And see also errata for it at page 2 of http://pages.cs.wisc.edu/~bach/errata.pdf

[charybdis]

Originally Posted by kriesel

Interesting stuff.
How useful would P+1 be, for wavefront Mersenne exponents?
I had thought the applicable factoring methods were already fully exploited by GIMPS.

P-1 is particularly useful for GIMPS because we can take advantage of the fact that all factors of 2^p-1 are of the form 2kp+1: we only need k to be smooth wrt B1/B2 in order to find the factor. P+1 doesn't have this advantage. It isn't even used much for smaller numbers (e.g. YAFU doesn't use it) because it tends to be more efficient to run ECM instead.