What's ECM?

[alpertron]

For example you want to find a factor q=1068367986947349161 of M1822669 (p=1822669):

Suppose that B1=50000, B2=5000000. P-1 can find easily the factor because q-1 = 2*2*2*5*661*4157*5333*1822669 (notice that a bound as small as B1 = 4157, B2 = 5333 would have sufficed).

For ECM after several tries you could find for example: q-155 = 2*3*19*43*1277*2617*2753*23689 and ECM would have found q with this curve (in this case a bound B1 = 2753, B2 = 23689 would have sufficed).

Notice that the fact that q-1 is multiple of p did not help ECM.

Unfortunately there is no way to find the value of x=155 in advance.

[LaurV]

Originally Posted by alpertron

This is incorrect. In ECM, the group order is different for each curve. Since the possible range for prime q (the factor of the Mersenne number) is q-2sqrt(q) to q+2sqrt(q), you should be very lucky to find the curve whose group order is q-1. Thus in general for the same B1/B2 bounds, ECM will not find the same factor than P-1 with the same bound.

Thanks for the intervention Dario, you are "ecm authority" (no irony, I really like your ecm implementations! very clear and straight), and your correction here is very welcomed, as it clarifies few things. However, let me point out, for other readers, not to confuse "P-1" with "P-1 modified for mersenne numbers". In your example you will need B1=5333 and B2=1822669 for "classic" P-1 to find the factor. I was talking about that one. With B1 = 4157, B2 = 5333, the "classic" P-1 will NOT find the factor - the "P-1 modified for mersenne numbers" will do. One more reason why is faster (already discussed). But then, to compare speed/etc, you have to use the same limits for ECM, B1=5333 and B2=1822669. Considering that, your second paragraph, and the later example, say exactly what I said. Inclusive the "10 times faster" part, which came also from that "2p" bundled into the modified P-1 (which we know in advance). If we try to run ECM with B1=4157, B2=5333, we may still find the factor, but we will need maaaaany curves. Depends on luck, in fact. One can try it with P95, just for fun, and tell us...

[alpertron]

Instead of running blindly Prime95, we can find smooth numbers near q, so I've written this program in UBASIC (this can run in 32-bit Windows systems).

   10   Q=1068367986947349161
   20   for X=1 to 100000
   30   Y=Q-X
   40   if Y@2=0 then Y=Y\2:goto 40:' ECM Step 1
   50   for Z=3 to 4157 step 2
   60   if Y@Z=0 then Y=Y\Z:goto 60
   70   next Z
   80   if Y<=5333 then print X;",";:' ECM Step 2
   90   next X

The values of x for which q-x are smooth in the range [0, 100000] are:

1481, 4981, 6786, 11999, 12913, 16766, 21786, 21901, 22521, 22711,
23291, 24650, 25878, 31006, 32111, 34211, 35974, 37110, 44544, 45959,
51727, 56376, 56993, 57151, 58076, 59814, 61145, 66476, 69375, 69442,
72673, 72914, 80579, 81051, 81098, 82638, 86523, 86757, 88334, 89036,
89561, 89754, 93111, 94349, 95214, 96561, 99367, 99601

There are 48 smooth numbers, so in average 1 of 2100 curves would succeed. This occurs because B2 = 5333 is extremely low.

[R.D. Silverman]

Originally Posted by alpertron

Instead of running blindly Prime95, we can find smooth numbers near q, so I've written this program in UBASIC (this can run in 32-bit Windows systems).

   10   Q=1068367986947349161
   20   for X=1 to 100000
   30   Y=Q-X
   40   if Y@2=0 then Y=Y\2:goto 40:' ECM Step 1
   50   for Z=3 to 4157 step 2
   60   if Y@Z=0 then Y=Y\Z:goto 60
   70   next Z
   80   if Y<=5333 then print X;",";:' ECM Step 2
   90   next X

The values of x for which q-x are smooth in the range [0, 100000] are:

1481, 4981, 6786, 11999, 12913, 16766, 21786, 21901, 22521, 22711,
23291, 24650, 25878, 31006, 32111, 34211, 35974, 37110, 44544, 45959,
51727, 56376, 56993, 57151, 58076, 59814, 61145, 66476, 69375, 69442,
72673, 72914, 80579, 81051, 81098, 82638, 86523, 86757, 88334, 89036,
89561, 89754, 93111, 94349, 95214, 96561, 99367, 99601

There are 48 smooth numbers, so in average 1 of 2100 curves would succeed. This occurs because B2 = 5333 is extremely low.

No, it is NOT extremely low. Here, we have B2 ~ q^(1/5). This is rather TYPICAL. For example, when searching for
60 digit factors it is very common to take B2 ~ 10^12 or so.

[alpertron]

Yes, while the calculations are correct, what I meant is that selecting B1=4157, B2=5333 is not a good idea, and B2 should be greater. For example, if we make B2 = 100 B1, so the step 2 takes about the same time than step 1, we get:

155, 188, 629, 641, 714, 779, 1052, 1481, 1488, 1865,
1880, 2663, 3148, 3226, 3351, 4187, 4461, 4799, 4981, 5661,
5950, 6464, 6481, 6692, 6786, 6983, 7150, 7306, 7318, 7374,
7417, 8279, 8837, 8936, 9186, 9236, 9465, 9555, 9636, 9916,
9953

I limited the values of x to be less than 10000 in this case. This time we get 41 smooth numbers, so 1 in 240 curves would be successful. This means that this time each curve needs twice the time, but the probability of finding the factor q is about 9 times better.

[alpertron]

Originally Posted by R.D. Silverman

No, it is NOT extremely low. Here, we have B2 ~ q^(1/5). This is rather TYPICAL. For example, when searching for
60 digit factors it is very common to take B2 ~ 10^12 or so.

Notice that since ECM timing is subexponential, not exponential, if the exponent 1/5 is correct for 60-digit factors, the exponent should be greater for smaller factors and smaller for finding prime factors with more digits.

[R.D. Silverman]

Originally Posted by alpertron

Notice that since ECM timing is subexponential, not exponential, if the exponent 1/5 is correct for 60-digit factors,

There is no such thing as either 'correct' or 'incorrect'. 1/5 is typical for current searches because it represents
a parameterization for the size of factors that we are looking for and for the composites we are currently working with.

the exponent should be greater for smaller factors and smaller for finding prime factors with more digits.

???? This is nonsense.

[alpertron]

Originally Posted by R.D. Silverman

???? This is nonsense.

If the timing for finding prime factors with ECM were always in the order of q^(1/5), that would make the algorithm exponential time. That means that for greater prime factors, the running time will be q^(1/10), q^(1/100), etc. So for extremely huge numbers, the exponent will tend to zero. By the same reasoning, for very small numbers, as the 19-digit prime number we are talking about, the value of B2 will be greater than q^(1/5) for optimal performance.

[R.D. Silverman]

Originally Posted by alpertron

If the timing for finding prime factors with ECM were always in the order of q^(1/5),

Hey moron. Where in my posts did I ever say "always on the order of q^(1/5)"???

Learn to read. I said that q^(1/5) is typical for the size of factors people are currently looking for and the
composites they are currently working on.

that would make the algorithm exponential time.

No shit, Sherlock.

Maybe you should try reading "A Practical Analysis of ECM".

You might then understand that the ASYMPTOTIC sub-exponential run time does
not mean "over a set of restricted sizes for the factors being sought". You might
also realize that the asymptotic sub-exponential run time does not depend on B2.
The choice of B2 ONLY affects the o(1) in the exponent. And the shape of o(1)
depends on many different variables.

[alpertron]

Originally Posted by R.D. Silverman

[...] Where in my posts did I ever say "always on the order of q^(1/5)"???

[...] I said that q^(1/5) is typical for the size of factors people are currently looking for and the
composites they are currently working on.

A few posts above you wrote:

No, it is NOT extremely low. Here, we have B2 ~ q^(1/5). This is rather TYPICAL. For example, when searching for
60 digit factors it is very common to take B2 ~ 10^12 or so.

So you are using optimal settings for 60-digit prime factors on a 19-digit one. The optimal B2 for the latter is greater than q^(1/5).

[R.D. Silverman]

Originally Posted by alpertron

A few posts above you wrote:

So you are using optimal settings for 60-digit prime factors on a 19-digit one. The optimal B2 for the latter is greater than q^(1/5).

You really need to learn how to discuss mathematics. You especially need to learn how to use quantifiers.
I discussed TYPICAL B2 values. I did not discuss anywhere whether these B2 values were OPTIMAL. (your apparent
interpretation of what I said.)

Learn to read. Learn how NOT to misquote others. Learn how NOT to put words in other peoples mouths. Learn how
[i]not[/b] to change their choice of quantifiers in your subsequent discussions.

Over a very wide range of factor sizes being sought , ECM behaves very much like an O(p^1/5) algorithm. Read the
"Practical Analysis" paper.

The choice of OPTIMAL B2 also depends on what optimization is being performed. If maximizing the probability of
success per unit time spent the analysis also assumes that one is going to perform a COMPLETE computation
for the parameter choices. Very few people perform a complete set of curves when looking for a p60 factor
among composites currently under consideration. OTOH, if one is going to spend a FIXED (or a priori bounded) amount
of time, the optimal B2 (and B1) will be different. If one performs a full (say) t60 search, finds nothing, then performs
a second t60 search it then means (post computation) that one has made sub-optimal B1, B2 choices.

Furthermore, the choice of OPTIMAL parameters very much depends not only on the underlying mathematical
theory but also upon practical matters: How much memory is there? What is its latency? How much L1, L2, L3
cache is available? If running on a multi-core processor, how many cores are running simultaneously? How much
cache contention is there? If running on multiple cores is there enough memory to allow the algorithm to
perform optimally? There certainly won't be enough cache.

My entire discussion throughout this thread has been to discuss typical choices. You have chosen to put
different words in my mouth. STOP.