mersenneforum.org > Data Understanding P+1
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2021-04-13, 18:39 #1 James Heinrich     "James Heinrich" May 2004 ex-Northern Ontario 1101001000012 Posts Understanding P+1 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?
2021-04-13, 19:19   #2
ATH
Einyen

Dec 2003
Denmark

2×1,567 Posts

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.

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

Last fiddled with by ATH on 2021-04-13 at 19:27

2021-04-13, 19:46   #3
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

1101001000012 Posts

Quote:
 Originally Posted by ATH From GMP-ECM "Readme":

 2021-04-13, 20:03 #4 ATH Einyen     Dec 2003 Denmark 2·1,567 Posts 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.
 2021-04-13, 20:18 #5 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 22×1,873 Posts 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: Code: 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: Code: P+1 found a factor in stage #2, B1=704001, B2=70400100. M4933 has a factor: 16237378233362413121723422738420712221935933479 (P+1, B1=704001, B2=70400100)
2021-04-13, 20:57   #6
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

1101001000012 Posts

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

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

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

2021-04-14, 00:04   #7
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

22·1,873 Posts

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

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

2021-04-14, 00:09   #8
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

22·1,873 Posts

Quote:
 Originally Posted by James Heinrich Code: 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.

2021-04-14, 01:44   #9
axn

Jun 2003

7·709 Posts

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

 2021-04-14, 02:46 #10 kriesel     "TF79LL86GIMPS96gpu17" Mar 2017 US midwest 22×3×7×61 Posts 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 Last fiddled with by kriesel on 2021-04-14 at 02:46
2021-04-14, 03:00   #11
charybdis

Apr 2020

263 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post hansl GMP-ECM 2 2019-05-31 01:16 Runtime Error Math 3 2019-03-24 00:56 Idgo Information & Answers 9 2018-11-28 10:49 Demonslay335 YAFU 11 2016-01-08 17:52 zacariaz Homework Help 32 2007-05-16 15:18

All times are UTC. The time now is 14:15.

Fri May 14 14:15:31 UTC 2021 up 36 days, 8:56, 0 users, load averages: 2.66, 2.30, 2.08