# 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$$.

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