Small-factor IFP / Heuristic · dependence on smallest factor

Factoring integers with elliptic curves

Hendrik W. Lenstra Jr.

Annals of Mathematics 1987

PublishedSource checked

Time bound: L_p[1/2, sqrt(2)] (log N)²
Space bound: Not extracted from the source

Source / version date: Nov 1987
Comparison variant: Heuristic · dependence on smallest factor
Cost scale: L_p[1/2,c] · poly(log N)
coefficientExact: sqrt(2)

Assumptions and source notes

Conjectured expected cost, where p is the least prime dividing N. This record measures dependence on the factor p, not general NFS complexity.

Source location

Abstract
Version: Version available at the cited URL; bibliographic metadata and stated bound checked on 2026-11-08

Primary source ↗

BibTeXDownload .bib

@article{lenstra87,
  author = {Hendrik W. Lenstra Jr.},
  title = {{Factoring integers with elliptic curves}},
  journal = {Annals of Mathematics 126(3), 649–673},
  year = {1987},
  doi = {10.2307/1971363},
  url = {https://annals.math.princeton.edu/1987/126-3/p09},
  keywords = {factoring, elliptic curve method, small prime factors},
  cr_date = {1987-11-30},
  cr_date_precision = {month},
  cr_status = {published},
  cr_venue = {Annals of Mathematics 126(3), 649–673},
  cr_author_ids = {hendrik-w-lenstra-jr}
}