Factoring integers with elliptic curves.

*(English)*Zbl 0596.10007
Preprint, Math. Inst. Univ. Amsterdam, No. 6218, 18 p. (1986).

Summary: 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 J. M. Pollard’s \(p-1\)-method [Proc. Camb. Philos. Soc. 76, 521–528 (1974; Zbl 0294.10005)] 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}\quad\text{for } x\to \infty.
\]
In the worst 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}\quad (\text{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\).