mersenneforum.org P+1 factoring explained
 Register FAQ Search Today's Posts Mark Forums Read

 2010-04-10, 03:02 #1 RichD     Sep 2008 Kansas 24·223 Posts P+1 factoring explained I was trying to factor "Cofactor of Quasi-repdigit 8(2)w9" at index 164. The number is 4521254810...<142>. So I looked at p+1, adding one to the end of the p number and asking factordb.com to Factorize. The result came up as: 2^5 * 389 * p138. Perfect candidate for P+1 factoring, so I thought. I tried ./ecm -pp1 @ 1e4, then 1e5, and finally 1e6. Nothing. What would be the ideal B1 (and/or B2) to factor this c142 number? Last fiddled with by RichD on 2010-04-10 at 03:37 Reason: Fix URLs
 2010-04-10, 06:42 #2 10metreh     Nov 2008 2×33×43 Posts You have misunderstood two things here. Firstly, p is the unknown factor, so p+1 is the factor+1. Secondly, the largest prime factor of p+1 must be below the B2 bound and the second largest must be below the B1 bound for the factor to be found. Thus the p138 ultimate factor is the exact opposite of what you want. Also, running P+1 once has a (IIRC) 50% chance of finding a factor with the right properties, unlike P-1 where it is 100%. That's why aliqueit always runs it 3 times. If you do want to factor it, there is still plenty of ECM at 3e6 to do. Last fiddled with by 10metreh on 2010-04-10 at 06:44
 2010-04-10, 12:03 #3 RichD     Sep 2008 Kansas 356810 Posts Wow! I did have a brain fart. It really is p+1 factoring, not N+1. Say the table was turned and the N-1 factors were 2^5 * 389 * p138. Have I totally misunderstood P-1 factoring also??
2010-04-10, 12:15   #4
RichD

Sep 2008
Kansas

24×223 Posts

Quote:
 Originally Posted by 10metreh If you do want to factor it, there is still plenty of ECM at 3e6 to do.
Which brings up another question. By starting at 3e6 will ECM still find a 25-30 digit factor, if one exists?

A few QuickECMs will flush out most any < 25 digit factors.

RichD.

2010-04-10, 13:18   #5
10metreh

Nov 2008

2×33×43 Posts

Quote:
 Originally Posted by RichD Say the table was turned and the N-1 factors were 2^5 * 389 * p138. Have I totally misunderstood P-1 factoring also??
Yes.

Quote:
 Originally Posted by RichD Which brings up another question. By starting at 3e6 will ECM still find a 25-30 digit factor, if one exists?
It will, but according to the page for this number on the near-repdigit website, ECM has been completed to 35 digits and 150 curves have been run at 3e6, leaving 2056 more at 3e6 to complete ECM to 40 digits. That should be more than enough ECM. Then run SNFS.

 2010-04-10, 14:50 #6 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 7·13·47 Posts P-1 finds a factor P when P-1 is: smooth to B1, except for up to one factor that's smooth to B2. P+1 has a good chance (~50% IIRC) of finding a factor P when P+1 is: smooth to B1, except for zero or one factor that's smooth to B2. ECM is similar, but instead of P-1 or P+1 being smooth to such and such, it's the group order of P given the randomly-selected sigma being smooth to such and such. They all can find factors smaller than they might normally be used to find. e.g. if P-1 could find a factor at B1=1e5 & B2=1e8, it will also be found at B1=1e9 (in step 1, no less!)...it'll just take far longer than is necessary. Similarly, ECM at B1=3e6 can find a 25-30 digit factor in a relatively low number of curves (expected for 25 digit factor: 11 curves), but it'll take far longer than is necessary. If the bounds are far larger than they ought to be, and the number hasn't already been checked for small factors, the chances are very good that you'll find a composite factor (maybe even N itself) which will then have to be factored separately. Last fiddled with by Mini-Geek on 2010-04-10 at 15:00
2010-04-10, 23:38   #8
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

7·13·47 Posts

Quote:
 Originally Posted by RichD If one is talking about a c100-c120+ number, is it better to start looking for 35, 40 or more digits given the above? In another words, is it better to start at the 35-45% level of the composite? Assuming the smaller factor (if there is just one) will eventually fall out.
No, that wouldn't be a good idea. It'd be simpler to run in some ways (you would only have to run at one set of B1/B2 values, but you'd have to include the newly-discovered small factors as you go along in order to avoid rediscovery and speed up the process), but almost always slower. (Unless, of course, you're reasonably sure that no small factors exist, in which case the question is not too different from already having run lower-bounds ECM.)
Why is this not a good idea? Let's say you're trying to factor a 110 digit number (like this one, which I'll be using for testing/timing purposes), and don't know if it has any factors (or, at least, don't know if it has any above a low trial factoring limit). Suppose it has a 20-digit factor. With B1=11e3, you'd expect to run 74 curves to find the factor. On my CPU, that'd take about 10.4 seconds. With B1=3e6, you can expect to find it in 3 curves, but each curve takes 29 seconds, so you don't expect to find it for 1.60 minutes. (don't ask me to explain the discrepancy between 29*3/60=1.45 and 1.60, I'm just reading off numbers from using ecm -v...maybe the 3 curve number was rounded down a large-ish amount) Clearly, if any 20-digit factors exist, it'd be far more economical to find them with B1=11e3, even though it would probably consist of running dozens of curves instead of just a 1-5.
Even if no 20-digit factor exists, you had a small chance in the 10.4 seconds you 'wasted' on B1=11e3 ECM to find larger factors (even though you would've had to run it for 49962 curves to expect a 30-digit chance, such things have happened). In any case, it's well worth the ~1.5 minutes you might've wasted by starting at B1=3e6.
Extending this thinking more fully, it's far more efficient to run each each 5-digit level's ECM in order than to skip straight to the 35-40

I've found this info with GMP-ECM's -v (verbose) command, which displays the sorts of stats that let me make the above analysis:
expected number of curves to find an n-digit factor, and
(once you've finished the curve so it knows how long you take) the expected time to find an n-digit factor.

Last fiddled with by Mini-Geek on 2010-04-10 at 23:45

 2010-04-11, 07:20 #9 10metreh     Nov 2008 2×33×43 Posts Alex (or someone who can hack GMP-ECM to give required curves for any number of digits), how many curves should it have taken (on average) to find my freak p41 with the parameters I used?
2010-04-11, 12:33   #10
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

176016 Posts

Quote:
 Originally Posted by 10metreh Alex (or someone who can hack GMP-ECM to give required curves for any number of digits), how many curves should it have taken (on average) to find my freak p41 with the parameters I used?
3647323 curves

All times are UTC. The time now is 01:57.

Sun May 22 01:57:25 UTC 2022 up 37 days, 23:58, 0 users, load averages: 1.34, 1.58, 1.59