# ECM Implementation is really slow

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 :/

• You can also consult this implementation which works but the code is rather... intricate. Nov 4 '12 at 2:00

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$)