ECM Implementation is really slow

Question

I followed the algorithms 14.4 (computes 1st and 3rd coordinates in (X,Y,Z)#k modulo n) and 14.5 (factorization using ECM) in David Bressoud's book 'Factorization and Primality Testing'. I think the algorithm is similar to Lenstra's, it uses the formula Y^2 - X^3 - aX, where the values for X,Y and a are chosen at random.

Here is my code in C++: http://pastebin.com/EnqCyJkk

I also found someone else's implementation of this algorithm, it's easier to read than mine: http://futureboy.us/frinksamp/ECM.frink

The program eventually finds factors, but it is really slow, I'm not sure if this is just a slow algorithm, I'm using the wrong parameters, or I have coded something incorrectly.

Any input would be really helpful, I've pretty much given up on this factoring obsession :/

Answer 1

I don't have David Bressoud's book, and so I can't say whether you made a mistake or he did. However, the algorithm you're using might come from the preliminary steps of Lenstra's method; however, it's missing the part that is designed to actually find the factors. In addition, as written, it can be shown (as written) to be lousy; not much better than trying random factors.

Here's the demonstration that it is a poor method:

Your method is to pick random values for $a$, $X$ and $Y$, and compute $GCD( n, P(a, X, Y))$ (where $P$ is a polynomial in the three variables $a$, $X$ and $Y$); you succeed if the $GCD$ is neither 1 nor $n$.

Another way of looking at it is that one of the necessary conditions for you to succeed is for $P(a, X, Y) = 0 \mod p$, where $p$ is one of the prime factors of $n$. However, if we consider $X$ and $Y$ fixed, then $P(a, X, Y)$ is a cubic polyinomial in $a$ (and is not the zero polynomial); such a polynomial has at most 3 zeros modulo a prime. That is, if we pick $X$ and $Y$ first, we have at most 3 value of $a \bmod p$ that will give us a solution; hence the probability of us picking such an $a$ is at most $3/p$. By symmetric, this also applies to the other prime factor $q$ of $n$ (assuming that there are only two), and hence the success probability per iteration is at most $3/p + 3/q$. This success probability is maybe a factor of 6 larger than picking a random value $r$ between 1 and $\sqrt{n}$, and checking if that's a factor (factor of 6 assuming $p \approx q$)

Answer 2

Here's the core issue. From what I can see, it sounds like the algorithm you implemented is not the ECM factoring algorithm. Therefore, you shouldn't be surprised if the algorithm you implemented is slow. If you want it to be faster, you should start by implementing the ECM factoring algorithm itself.

@poncho's answer gives a more detailed explanation of why we should expect the algorithm you implemented to be slow.