Abstract
This paper is devoted to the description and analysis of a new algorithm to factor positive integers. It depends on the use of elliptic curves. The new method is obtained from Pollard’s $(p-1)$-method (Proc. Cambridge Philos. Soc. $\mathbf{76}$ (1974), 521–528) by replacing the multiplicative group by the group of points on a random elliptic curve. It is conjectured that the algorithm determines a non-trivial divisor of a composite number $n$ in expected time at most $K(p)(\log n)^2$, where $p$ is the least prime dividing $n$ and $K$ is a function for which $\log K(x) = \sqrt{(2+o(1))\log x\log\log x}$ for $x\to \infty$. In the worse case, when $n$ is the product of two primes of the same order of magnitude, this is $\exp((1+o(1))\sqrt{\log n\log\log n}$ (for $n\to \infty$). There are several other factoring algorithms of which the conjectural expected running time is given by the latter formula. However, these algorithms have a running time that is basically independent of the size of the prime factors of $n$, whereas the new elliptic curve method is substantially faster for small $p$.
