20210413, 18:39  #1 
"James Heinrich"
May 2004
exNorthern Ontario
2^{5}×3×5×7 Posts 
Understanding P+1
I'm passingly familiar with P1, 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? 
20210413, 19:19  #2  
Einyen
Dec 2003
Denmark
31·101 Posts 
From a practical standpoint it is almost the same as P1. 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 23 P+1 tests with the same B1 and B2, which is useless for P1. Generally P+1 tests are slower than P1 tests with the same B1 and B2, I do not remember by how much, it was a long time since I ran either. From GMPECM "Readme": Quote:
Last fiddled with by ATH on 20210413 at 19:27 

20210413, 19:46  #3 
"James Heinrich"
May 2004
exNorthern Ontario
2^{5}·3·5·7 Posts 

20210413, 20:03  #4 
Einyen
Dec 2003
Denmark
31×101 Posts 
Because the need to run 23 P+1 tests at each B1 and the tests taking longer, generally people do not run as much P+1 as P1 before moving on to ECM.

20210413, 20:18  #5 
P90 years forever!
Aug 2002
Yeehaw, FL
3·11·227 Posts 
P+1 stage 1 would be a little less than twice as slow as P1 stage 1.
P+1 stage 2 would be a little faster than P1 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) Code:
P+1 found a factor in stage #2, B1=704001, B2=70400100. M4933 has a factor: 16237378233362413121723422738420712221935933479 (P+1, B1=704001, B2=70400100) 
20210413, 20:57  #6 
"James Heinrich"
May 2004
exNorthern Ontario
2^{5}·3·5·7 Posts 
I understand how to get from a P1 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 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? 
20210414, 00:04  #7  
P90 years forever!
Aug 2002
Yeehaw, FL
3·11·227 Posts 
Caveat: I'm not a P+1 expert.
Quote:
With P+1, factors are of the form f=2k1. We find a factor f when k=(f+1)/2 is B1/B2smooth 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/B2smooth 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/B2smooth 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. 

20210414, 00:09  #8  
P90 years forever!
Aug 2002
Yeehaw, FL
3×11×227 Posts 
Quote:
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 P1 factors. That is, the algorithm is part P+1 and part P1. 

20210414, 01:44  #9  
Jun 2003
2×3×827 Posts 
Quote:


20210414, 02:46  #10 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
5,119 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 P1 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 P1, P+1 would go first, and then a determination whether it was in effect a slow P1, since it seems pointless to do P1 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...09474671.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 20210414 at 02:46 
20210414, 03:00  #11 
Apr 2020
263_{10} Posts 
P1 is particularly useful for GIMPS because we can take advantage of the fact that all factors of 2^p1 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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Recommendations for understanding ECM?  hansl  GMPECM  2  20190531 01:16 
Understanding Mersenne PRP  Runtime Error  Math  3  20190324 00:56 
Understanding status info  Idgo  Information & Answers  9  20181128 10:49 
Understanding NFS  Demonslay335  YAFU  11  20160108 17:52 
LL Test: Understanding the math  zacariaz  Homework Help  32  20070516 15:18 