ECM question

[bcp19]

I found a TF factor that P-1 would never find (~2.6 million GHzD) and I was wondering approx how long it should take for ECM to find it. The P-1 parameters would be B1=3 and B2=~1.42e+13.

I know the 'normal' B1/B2 for a ~25 digit number is 50,000/5,000,000. Would this indicate this factor could not be found by ECM?

[bsquared]

Originally Posted by bcp19

I found a TF factor that P-1 would never find (~2.6 million GHzD) and I was wondering approx how long it should take for ECM to find it. The P-1 parameters would be B1=3 and B2=~1.42e+13.

I know the 'normal' B1/B2 for a ~25 digit number is 50,000/5,000,000. Would this indicate this factor could not be found by ECM?

ECM doesn't care about the factorization of P-1, only about the size of the factor. If the factor is ~25 digits, then with B1=50k there is about a 37% chance (1 / exp(1)) of missing the factor after running a couple hundred curves (GMP-ECM reports 221, but that's with a much large B2). Run twice as many curves and the chance of missing it goes to about 14% (1 / exp(2)), and so on.

[R.D. Silverman]

Originally Posted by bsquared

ECM doesn't care about the factorization of P-1, only about the size of the factor. If the factor is ~25 digits, then with B1=50k there is about a 37% chance (1 / exp(1)) of missing the factor after running a couple hundred curves (GMP-ECM reports 221, but that's with a much large B2). Run twice as many curves and the chance of missing it goes to about 14% (1 / exp(2)), and so on.

If people (who profess an interest in this subject) would ever actually
READ what has been written, they wouldn't have to ask such questions.

My joint paper with Sam Wagstaff Jr. should be REQUIRED READING
for anyone who wants to discuss ECM.

I ask: why wouldn't anyone interested in this subject want to read it?
Is the answer: laziness? Or is it that the claim of interest is a shallow one?

[bsquared]

Originally Posted by R.D. Silverman

If people (who profess an interest in this subject) would ever actually
READ what has been written, they wouldn't have to ask such questions.

My joint paper with Sam Wagstaff Jr. should be REQUIRED READING
for anyone who wants to discuss ECM.

I ask: why wouldn't anyone interested in this subject want to read it?
Is the answer: laziness? Or is it that the claim of interest is a shallow one?

[IMO] Why should anyone have to learn how to design/fabricate the modulation circuitry surrounding an IR light emitting diode just to turn on their TV? They just want to know what buttons to press (note to BCP - this may not pertain to you... it is a general answer).

Now pretend that the instruction manual to their remote control exists only in scavenger hunt form, where they follow one clue to another clue to another clue, etc., until they can learn how to turn on their TV. That is close to how it is with advanced number theory software - tools that are fun to use but that have widely-dispersed, partially-hidden, and variable-content instruction manuals. This forum provides a short-cut through much of that.

If someone following the short cut discovers something shiny along the way, and goes off and learns some number theory as a result, then that's a bonus, but not necessarily the primary purpose of this forum. As such your link to your paper is great, but your comments not so much. [/IMO]

[R.D. Silverman]

Originally Posted by bsquared

[IMO] Why should anyone have to learn how to design/fabricate the modulation circuitry surrounding an IR light emitting diode just to turn on their TV? They just want to know what buttons to press (note to BCP - this may not pertain to you... it is a general answer).

But the OP was not doing that! He wasn't asking what buttons to push to
run the software.

He was asking about the capabilities of the algorithm!!!!

[bsquared]

Originally Posted by R.D. Silverman

But the OP was not doing that! He wasn't asking what buttons to push to
run the software.

He was asking about the capabilities of the algorithm!!!!

A request for functional specifications of an algorithm does not equal a request for in-depth knowledge of the innards of it, so I think there is still a distinction.

But like I said, I'm not taking exception with you trying to get people to learn about the algorithm, I'm taking exception with your methods.

[bcp19]

Originally Posted by R.D. Silverman

If people (who profess an interest in this subject) would ever actually
READ what has been written, they wouldn't have to ask such questions.

My joint paper with Sam Wagstaff Jr. should be REQUIRED READING
for anyone who wants to discuss ECM.

I ask: why wouldn't anyone interested in this subject want to read it?
Is the answer: laziness? Or is it that the claim of interest is a shallow one?

<sigh> I agree with bsquared here, why do I have to reinvent the wheel in order to drive a car? Millions of engineers have already put billions of hours of research into building cars, yet I should drop everything and start at square one so as to not be lazy and answer my own questions.

So, to put it simply yet verbosely, while trial factoring 63186931 I found a 72.184 bit factor of length 22 digits. In the expression 2kp-1, k = 3 × 14154475893511. From scratch this TF would take a little over 30 GHzD to be found. As I stated P-1 would take over 2.6 million GHzD. While I understand ECM is largely dependant on luck time-wise when it comes to finding a factor since it could be found on Curve 1 or Curve 1001, I was curious if this factor could even be found under normal 25 digit length B1/B2 parameters. When I plugged this exponent into P95 with a B1 of 50,000 and 300 curves (which seems to be the recommended amount) it said the run would last 63 days on my laptop. I didn't feel like waiting that long (or wasting those resources) to see if it would find it, so I felt it was time to ask the experts.

You may also note I did not ask this question in the MATH section, where I was sure I'd get a lecture. But, hey, lectures seem to find me.

[Mini-Geek]

Originally Posted by bcp19

...of length 22 digits. ... I was curious if this factor could even be found under normal 25 digit length B1/B2 parameters

With almost no exception, the answer to the question "could ECM possibly find this factor?" is "yes". The answer to the question "could ECM possibly fail to find this factor?" is also, with almost no exception, "yes". The only issue is how long you should expect it to take; or to put it another way, how lucky you have to be to find it in a reasonable amount of time.
The answer to "is ECM at digit level x the best general-purpose way a good way to find this factor of size y?" is yes if x is close to y (no more than 3** apart).

Originally Posted by bcp19

When I plugged this exponent into P95 with a B1 of 50,000 and 300 curves (which seems to be the recommended amount) it said the run would last 63 days on my laptop.

Since 22 is smaller than 25, the actual amount of curves expected* is lower than 300; let's say 100**. 100 curves is 357 GHz-days. However, let's assume this was ECMd like ECM is usually run, going up subsequent digit levels for an efficient search. The 20-digit level (B1=11000, 90 curves, 70 GHz-days) had a decent chance of finding it. Thus you could expect to spend about 200** GHz-days. If you were to put, say, 95% confidence lower and upper bounds on how many GHz-days it should take to find, it'd be a VERY wide range**. Still, it's easy to see that it's somewhere between P-1 (~4 GHz-days) and TF (~2.6 million GHz-days), much closer to P-1, but still impractical.

If you knew in advance that the factor was 22 digits, you could choose a B1 that optimized that digit level, and maybe find it in about expected 150** GHz-days.

* "expected" being the same as what bsquared defined earlier: there is about a 37% chance (1 / exp(1)) of missing the factor after running enough curves to expect to find the factor.
** Numbers marked with this have been made up on the spot, and may be wildly inaccurate, but can help give you an idea of what you're dealing with.

[ATH]

Now that you know the factor, you use the Magma Calculator to check which B1/B2 would be required for random sigma values:

http://magma.maths.usyd.edu.au/calc/

Just paste this code in and change the sigma value s at the bottom to a random (32 bit I think) number.

FindGroupOrder2 := function (p, s)
   K := GF(p);
   v := K ! (4*s);
   u := K ! (s^2-5);
   x := u^3;
   b := 4*x*v;
   a := (v-u)^3*(3*u+v);
   A := a/b-2;
   x := x/v^3;
   b := x^3 + A*x^2 + x;
   E := EllipticCurve([0,b*A,0,b^2,0]);
   return FactoredOrder(E);
end function;

p := 5366267349746657428447;
s := 10000;
FindGroupOrder2(p, s);

For s:=10000 the group order is:
[ <2, 4>, <3, 1>, <5, 1>, <57223, 1>, <16530659, 1>, <23637431, 1> ]

The last 2 digits is the B1 and B2 value required to find the factor with sigma = 10000, so B1 = 17e6 and B2=24e6.

So you can just try random sigma values to see how low you can find B1/B2.

You can also download the Magma Calculator but I haven't tried that.

[Mini-Geek]

Originally Posted by Mini-Geek

Still, it's easy to see that it's somewhere between P-1 (~4 GHz-days) and TF (~2.6 million GHz-days), much closer to P-1, but still impractical.

Correction: TF (8.6) and P-1 (2.6 million), with ECM's range being closer to TF.

I had momentarily confused your case for the more commonly-noted case of a large P-1 factor, where P-1 is the quick way and TF is the slow way. E.g. this factor I found that, at 41 digits, would take 1.24 GHz-days of P-1 or 18 quintillion (1.8*10^19) GHz-days of TF.

[R.D. Silverman]

Originally Posted by Mini-Geek

<snip>

If you knew in advance that the factor was 22 digits, you could choose a B1 that optimized that digit level, and maybe find it in about expected 150** GHz-days.

Once again, if people BOTHERED TO READ MY PAPER, they would find that it
discusses HOW to select parameters when the size of the factor is unknown.

After running some trials one uses information from the ECM FAILURE,
and the theoretical distribution of factor sizes along with BAYES THEOREM
to reselect parameters in an optimal way.