This paper gives a factorization method, which uses the multiplicative groups of elliptic curves over finite fields. The factorization method is probabilistic, with a conjectured expected running time for the factorization of n to be at most \((\log n)^ 2 \exp ((1+o(1))\sqrt{\log n\quad \log \log n}),\) for \(n\to \infty\). If the smallest prime factor of n is much smaller than \(\sqrt{n}\), the running time is expected to be shorter.
The elliptic curve factoring method is inspired by Pollard’s (p-1) factoring method. Instead of using the multiplicative group ( \({\mathbb{Z}}/n{\mathbb{Z}})^*\) in the Pollard method, the multiplicative group of an elliptic curve over \({\mathbb{Z}}/n{\mathbb{Z}}\) is used. Since the author does not want (and does not need) to go into the details of elliptic curves over finite rings he treats only elliptic curves over finite fields. In fact he only needs results for fields with a prime number of elements. Let \({\mathbb{F}}_ p\) be the finite field with p elements. The paper gives facts about the number of elliptic curves, over \({\mathbb{F}}_ p\), whose number of points is in a given subset of \({\mathbb{N}}\). Moreover he computes how many numbers in a given interval of \({\mathbb{N}}\) are completely composed of small prime factors. These results are combined to compute the expected run time of the algorithm. Unfortunately in this computation an unproven conjecture from analytic number theory was needed. However, it seems that the conjecture is true.
At the end of the paper a comparison is made between the elliptic curve method and other factoring methods. One of the advantages of the elliptic curve method is that the storage requirements are much less than those for other methods of the same expected run time. It appears that the elliptic curve method is the fastest factorization method, with an exception for the quadratic sieve, for numbers composed of two prime numbers of about the same size. In addition, it seems favorable to use the elliptic curve method as a subroutine for other factoring methods.