zbMATH — the first resource for mathematics

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\).

11Y05 Factorization
11Y16 Number-theoretic algorithms; complexity
11G05 Elliptic curves over global fields
68Q25 Analysis of algorithms and problem complexity