Factoring integers with elliptic curves
type: Item
instance of: scholarly article
title: Factoring integers with elliptic curves
zbMATH Open document ID: 0629.10006
DOI: 10.2307/1971363
published in: Annals of Mathematics. Second Series
publication date: 1987-01-01T00:00:00Z
review text: 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 …
Mathematics Subject Classification ID: 11A41
Mathematics Subject Classification ID: 11-04
Mathematics Subject Classification ID: 14H52
Mathematics Subject Classification ID: 14G15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4023368
zbMATH Keywords: computational number theory
zbMATH Keywords: elliptic curve method
zbMATH Keywords: probabilistic algorithm
zbMATH Keywords: factorization method
zbMATH Keywords: multiplicative groups of elliptic curves over finite fields
zbMATH Keywords: running time
zbMATH Keywords: comparison
author: H. W. jun. Lenstra
MaRDI profile type: Publication
OpenAlex ID: W2005317356
Wikidata QID: Q55899111
Recommended article: Q3728067
Recommended article: Elliptic curve and integer factorization
Recommended article: Q4282968
Recommended article: Q4807910
Recommended article: Q3499667
Recommended article: Integer factoring problem and elliptic curves over the ring $\mathbb Z_n$
Recommended article: Q4737509
Recommended article: Q4285042
Recommended article: Q4273681
description: scientific article; zbMATH DE number 4023368