P+1 factoring explained

[RichD]

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?

[10metreh]

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.

[RichD]

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

[RichD]

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.

[10metreh]

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.

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.

[Mini-Geek]

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.

[RichD]

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

[Mini-Geek]

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.

[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?

[henryzz]

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