Lenstra's Elliptic Curve Factorization Method

Figure 6.4: Hendrik Lenstra

Algorithm 6.3 (Elliptic Curve Factorization Method)   Given a positive integer $N$ and a bound $B$ , this algorithm attempts to find a nontrivial factor $m$ of $N$ . Carry out the following steps:

1. [Compute lcm] Use Algorithm 6.3.2 to compute $m=\lcm (1,2,\ldots, B)$ .
2. [Choose Random Elliptic Curve] Choose a random $a\in \mathbb{Z}/N\mathbb{Z}{}$ such that $4a^3+27\in(\mathbb{Z}/N\mathbb{Z}{})^*$ . Then $P=(0,1)$ is a point on the elliptic curve $y^2=x^3+ax+1$ over $\mathbb{Z}/N\mathbb{Z}{}$ .
3. [Compute Multiple] Attempt to compute $m P$ using an elliptic curve analogue of Algorithm 2.3.13. If at some point we cannot compute a sum of points because some denominator in step 3 of Algorithm 6.2.1 is not coprime to $N$ , we compute the $\gcd$ of this denominator with $N$ . If this $\gcd$ is a nontrivial divisor, output it. If every denominator is coprime to $N$ , output ``Fail''.

If Algorithm 6.3.8 fails for one random elliptic curve, there is an option that is unavailable with Pollard's $(p-1)$ -method--we may repeat the above algorithm with a different elliptic curve. With Pollard's method we always work with the group $(\mathbb{Z}/N\mathbb{Z}{})^*$ , but here we can try many groups $E(\mathbb{Z}/N\mathbb{Z}{})$ for many curves $E$ . As mentioned above, the number of points on $E$ over $\mathbb{Z}/p\mathbb{Z}{}$ is of the form $p+1-t$ for some $t$ with $\vert t\vert<2\sqrt{p}$ ; Algorithm 6.3.8 thus has a chance if $p+1-t$ is $B$ -power-smooth for some $t$ with $\vert t\vert<2\sqrt{p}$ .