mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Data

Reply
 
Thread Tools
Old 2021-04-13, 18:39   #1
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

2×3×569 Posts
Default 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?
James Heinrich is offline   Reply With Quote
Old 2021-04-13, 19:19   #2
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

315710 Posts
Default

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":

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
ATH is offline   Reply With Quote
Old 2021-04-13, 19:46   #3
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

2×3×569 Posts
Default

Quote:
Originally Posted by ATH View Post
From GMP-ECM "Readme":
Helpful, thank you.
James Heinrich is offline   Reply With Quote
Old 2021-04-13, 20:03   #4
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

7×11×41 Posts
Default

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.
ATH is offline   Reply With Quote
Old 2021-04-13, 20:18   #5
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

11101011010012 Posts
Default

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)
Prime95 is offline   Reply With Quote
Old 2021-04-13, 20:57   #6
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

65268 Posts
Default

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 View Post
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?
James Heinrich is offline   Reply With Quote
Old 2021-04-14, 00:04   #7
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

7,529 Posts
Default

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

Quote:
Originally Posted by James Heinrich View Post
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 is offline   Reply With Quote
Old 2021-04-14, 00:09   #8
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

1D6916 Posts
Default

Quote:
Originally Posted by James Heinrich View Post

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.
Prime95 is offline   Reply With Quote
Old 2021-04-14, 01:44   #9
axn
 
axn's Avatar
 
Jun 2003

10011110100102 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
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.
axn is online now   Reply With Quote
Old 2021-04-14, 02:46   #10
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

10101000011102 Posts
Default

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
kriesel is online now   Reply With Quote
Old 2021-04-14, 03:00   #11
charybdis
 
charybdis's Avatar
 
Apr 2020

16616 Posts
Default

Quote:
Originally Posted by kriesel View Post
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.
charybdis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Recommendations for understanding ECM? hansl GMP-ECM 2 2019-05-31 01:16
Understanding Mersenne PRP Runtime Error Math 3 2019-03-24 00:56
Understanding status info Idgo Information & Answers 9 2018-11-28 10:49
Understanding NFS Demonslay335 YAFU 11 2016-01-08 17:52
LL Test: Understanding the math zacariaz Homework Help 32 2007-05-16 15:18

All times are UTC. The time now is 13:44.


Sun Jul 25 13:44:34 UTC 2021 up 2 days, 8:13, 1 user, load averages: 2.07, 1.94, 1.96

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.