Suppose $n=pq$ is a number we wish to factor. Choose a random elliptic curve mod $n$ and a point on the curve. In practice, one chooses several (around 14 for numbers around 50 digits; more for larger integers) curves with points and runs the algorithm in parallel.

How do we choose the curve? First, choose a point $P$ and a coefficient $b\text{.}$ Then choose $c$ so that $P$ lies on the curve $y^2=x^3+bx+c\text{.}$ This is much more efficient than choosing $b$ and $c$ and then trying to find a point.

For example, let $n=2773\text{.}$ Take $P=(1\text{,}3)$ and $b=4\text{.}$ Since we want $3^2\equiv 1^3+4\cdot 1+c\text{,}$ we take $c=4\text{.}$ Therefore, our curve is

We calculated $2P=(1771\text{,}705)$ in a previous example. Note that during the calculation, we needed to find $6^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}2773)\text{.}$ This required that $gcd(6\text{,}2773)=1$ and used the extended Euclidean algorithm, which was essentially a gcd calculation.

Now let’s calculate $3P=2P+P\text{.}$ The line through the points $2P=(1771\text{,}705)$ and $P=(1\text{,}3)$ has slope 702/1770. When we try to invert 1770 mod 2773, we find that $gcd(1770\text{,}2773)=59\text{,}$ so we cannot do this. So what do we do? Our original goal was to factor 2773, so we don’t need to do anything more. We have found the factor 59, which yields the factorization $2773=59\cdot 47\text{.}$

Here’s what happened. Using the Chinese remainder theorem, we can regard $E$ as a pair of elliptic curves, one mod 59 and the other mod 47. It turns out that $3P=\text{∞}(\mathrm{m}\mathrm{o}\mathrm{d}59)\text{,}$ while $4P=\text{∞}(\mathrm{m}\mathrm{o}\mathrm{d}47)\text{.}$ Therefore, when we tried to compute $3P\text{,}$ we had a slope that was infinite mod 59 but finite mod 47. In other words, we had a denominator that was 0 mod 59 but nonzero mod 47. Taking the gcd allowed us to isolate the factor 59.

The same type of idea is the basis for many factoring algorithms. If $n=pq\text{,}$ you cannot separate $p$ and $q$ as long as they behave identically. But if you can find something that makes them behave slightly differently, then they can be separated. In the example, the multiples of $P$ reached $\text{∞}$ faster mod 59 than mod 47. Since in general the primes $p$ and $q$ should act fairly independently of each other, one would expect that for most curves $E(\mathrm{m}\mathrm{o}\mathrm{d}pq)$ and points $P\text{,}$ the multiples of $P$ would reach $\text{∞}$ mod $p$ and mod $q$ at different times. This will cause the gcd to find either $p$ or $q\text{.}$

Usually, it takes several more steps than 3 or 4 to reach $\text{∞}$ mod $p$ or mod $q\text{.}$ In practice, one multiplies $P$ by a large number with many small prime factors, for example, 10000!. This can be done via successive doubling (the additive analog of successive squaring; see Exercise 21). The hope is that this multiple of $P$ is $\text{∞}$ either mod $p$ or mod $q\text{.}$ This is very much the analog of the $p-1$ method of factoring. However, recall that the $p-1$ method (see Section 9.4) usually doesn’t work when $p-1$ has a large prime factor. The same type of problem could occur in the elliptic curve method just outlined when the number $m$ such that $mP$ equals $\text{∞}$ has a large prime factor. If this happens (so the method fails to produce a factor after a while), we simply change to a new curve $E\text{.}$ This curve will be independent of the previous curve and the value of $m$ such that $mP=\text{∞}$ should have essentially no relation to the previous $m\text{.}$ After several tries (or if several curves are treated in parallel), a good curve is often found, and the number $n=pq$ is factored. In contrast, if the $p-1$ method fails, there is nothing that can be changed other than using a different factorization method.

For more examples, see Examples 45 and 46 in the Computer Appendices.

In general, consider an elliptic curve $E(\mathrm{m}\mathrm{o}\mathrm{d}p)$ for some prime $p\text{.}$ The smallest positive $m$ such that $mP=\text{∞}$ on this curve divides the number $N$ of points on $E(\mathrm{m}\mathrm{o}\mathrm{d}p)$ (if you know group theory, you’ll recognize this as a corollary of Lagrange’s theorem), so $NP=\text{∞}\text{.}$ Quite often, $m$ will be $N$ or a large divisor of $N\text{.}$ In any case, if $N$ is a product of small primes, then $B!$ will be a multiple of $N$ for a reasonably small value of $B\text{.}$ Therefore, $B!P=\text{∞}\text{.}$

A number that has only small prime factors is called smooth. More precisely, if all the prime factors of an integer are less than or equal to $B\text{,}$ then it is called B-smooth. This concept played a role in the $x^2\equiv y^2$ method and the $p-1$ factoring method (Section 9.4), and the index calculus attack on discrete logarithms (Section 10.2).

Recall from Hasse’s theorem that $N$ is an integer near $p\text{.}$ It is possible to show that the density of smooth integers is large enough (we’ll leave small and large undefined here) that if we choose a random elliptic curve $E(\mathrm{m}\mathrm{o}\mathrm{d}p)\text{,}$ then there is a reasonable chance that the number $N$ is smooth. This means that the elliptic curve factorization method should find $p$ for this choice of the curve. If we try several curves $E(\mathrm{m}\mathrm{o}\mathrm{d}n)\text{,}$ where $n=pq\text{,}$ then it is likely that at least one of the curves $E(\mathrm{m}\mathrm{o}\mathrm{d}p)$ or $E(\mathrm{m}\mathrm{o}\mathrm{d}q)$ will have its number of points being smooth.

In summary, the advantage of the elliptic curve factorization method over the $p-1$ method is the following. The $p-1$ method requires that $p-1$ is smooth. The elliptic curve method requires only that there are enough smooth numbers near $p$ so that at least one of some randomly chosen integers near $p$ is smooth. This means that elliptic curve factorization succeeds much more often than the $p-1$ method.

The elliptic curve method seems to be best suited for factoring numbers of medium size, say around 40 or 50 digits. These numbers are no longer used for the security of factoring-based systems such as RSA, but it is sometimes useful in other situations to have a fast factorization method for such numbers. Also, the elliptic curve method is effective when a large number has a small prime factor, say of 10 or 20 decimal digits. For large numbers where the prime factors are large, the quadratic sieve and number field sieve are superior (see Section 9.4).