Factoring integers with elliptic curves. (English) Zbl 0596.10007

Lenstra, H. W. jun.

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

MSC:

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

Keywords:

computational number theory; factoring algorithms; elliptic curve method

Citations:

Zbl 0294.10005