Motivation for the Elliptic Curve Method

Fix a positive integer $B$ . If $N=pq$ with $p$ and $q$ prime and $p-1$ and $q-1$ are not $B$ -power smooth, then the Pollard $(p-1)$ -method is unlikely to work. For example, let $B=20$ and suppose that $N=59\cdot 101 = 5959$ . Note that neither  $59-1=2\cdot29$ nor $101-1=4\cdot 25$ is $B$ -power smooth. With $m=\lcm (1,2,3,\ldots,20)=232792560$ , we have

$$2^m - 1 \equiv 5944\pmod{N},$$

and $\gcd(2^m-1,N)=1$ , so we do not find a factor of $N$ .

As remarked above, the problem is that $p-1$ is not $20$ -power smooth for either $p=59$ or $p=101$ . However, notice that $p-2=3\cdot 19$ is $20$ -power smooth. Lenstra's ECM replaces $(\mathbb{Z}/p\mathbb{Z}{})^*$ , which has order $p-1$ , by the group of points on an elliptic curve $E$ over $\mathbb{Z}/p\mathbb{Z}{}$ . It is a theorem that

$$\char93 E(\mathbb{Z}/p\mathbb{Z}{}) =p+1\pm s$$

for some nonnegative integer $s<2\sqrt{p}$ (see e.g., [#!silverman:aec!#, §V.1] for a proof). (Also every value of $s$ subject to this bound occurs, as one can see using ``complex multiplication theory''.) For example, if $E$ is the elliptic curve

$$y^2 = x^3 + x + 54$$

over $\mathbb{Z}/59\mathbb{Z}{}$ then by enumerating points one sees that $E(\mathbb{Z}/59\mathbb{Z}{})$ is cyclic of order $57$ . The set of numbers $59+1\pm s$ for $s\leq 15$ contains $14$ numbers that are $B$ -power smooth for $B=20$ .Thus working with an elliptic curve gives us more flexibility. For example, $60=59+1+0$ is $5$ -power smooth and $70 = 59+1+10$ is $7$ -power smooth.