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