20100410, 03:02  #1 
Sep 2008
Kansas
2^{4}·223 Posts 
P+1 factoring explained
I was trying to factor "Cofactor of Quasirepdigit 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 20100410 at 03:37 Reason: Fix URLs 
20100410, 06:42  #2 
Nov 2008
2×3^{3}×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 P1 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 20100410 at 06:44 
20100410, 12:03  #3 
Sep 2008
Kansas
3568_{10} Posts 
Wow! I did have a brain fart.
It really is p+1 factoring, not N+1. Say the table was turned and the N1 factors were 2^5 * 389 * p138. Have I totally misunderstood P1 factoring also?? 
20100410, 12:15  #4 
Sep 2008
Kansas
2^{4}×223 Posts 

20100410, 13:18  #5  
Nov 2008
2×3^{3}×43 Posts 
Quote:
Quote:


20100410, 14:50  #6 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
7·13·47 Posts 
P1 finds a factor P when P1 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 P1 or P+1 being smooth to such and such, it's the group order of P given the randomlyselected sigma being smooth to such and such. They all can find factors smaller than they might normally be used to find. e.g. if P1 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 2530 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 MiniGeek on 20100410 at 15:00 
20100410, 22:18  #7 
Sep 2008
Kansas
6760_{8} Posts 
Boy, do I look stupid. I remember reading about all this a couple years ago. Since I haven't done much programming lately, it started to go by the wayside.
When someone would post a significant find, others would chime in and explain the optimum bounds or the properties of p (smooth). Then why didn't the OP use those optimum bounds? Didn't they do enough research instead of randomly running curves? Well, this is all hindsight because once you know the answer, you know the quickest way to find it based on the use of the bounds inside ECM. So yes, p is based off the answer one is looking for. Not knowing the p beforehand causes a lot of random searching for the answer. Once the answer is known, it can easily be explained or reproduced in a timely fashion. I'm starting to answer my next question. In the documentation for ECM it implies, What size factor is one looking for? Then use these bounds and number of curves. Again, not knowing the answer ahead of time, I want to start at 40 (digits). So what if the factor is composite, msieve will decompose it in milliseconds. I just saved hundreds of curves by not starting at B1=11e3. But running one curve at 3e6 could be equivalent to running the whole set at 11e3. If one is talking about a c100c120+ 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 3545% level of the composite? Assuming the smaller factor (if there is just one) will eventually fall out. 
20100410, 23:38  #8  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
7·13·47 Posts 
Quote:
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 20digit 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 largeish amount) Clearly, if any 20digit 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 15. Even if no 20digit 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 30digit 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 5digit level's ECM in order than to skip straight to the 3540 I've found this info with GMPECM's v (verbose) command, which displays the sorts of stats that let me make the above analysis: expected number of curves to find an ndigit factor, and (once you've finished the curve so it knows how long you take) the expected time to find an ndigit factor. Last fiddled with by MiniGeek on 20100410 at 23:45 

20100411, 12:33  #10  
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
1760_{16} Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
japan catastroph explained to kids  firejuggler  Lounge  15  20110323 05:17 
Prime95 worktodo.ini parameters not explained  azhad  Software  2  20080531 23:38 