IFP / Special form · heuristic · L(1/3)

The number field sieve

Arjen K. Lenstra · Hendrik W. Lenstra Jr. · Mark S. Manasse · John M. Pollard

STOC 1990

PublishedSource checked

Time bound: L_N[1/3, (32/9)^1/3]
Space bound: Not extracted from the source

Source / version date: 1990
Comparison variant: Special form · heuristic · L(1/3)
Cost scale: L_N[1/3,c]
coefficientExact: (32/9)^{1/3}

Assumptions and source notes

The paper explicitly assumes N = r^e ± s with bounded r and |s|; this number-theoretic structure is essential. The expected-time analysis is heuristic.

Source location

Introduction, equation (1.1)
Version: Version available at the cited URL; bibliographic metadata and stated bound checked on 2026-11-08

Primary source ↗

BibTeXDownload .bib

@incollection{llmp90,
  author = {Arjen K. Lenstra and Hendrik W. Lenstra Jr. and Mark S. Manasse and John M. Pollard},
  title = {{The number field sieve}},
  booktitle = {STOC 1990},
  year = {1990},
  doi = {10.1145/100216.100295},
  url = {https://wstein.org/129/references/Lenstra-Lenstra-Manasse-Pollard-The%20number%20field%20sieve.pdf},
  keywords = {factoring, number field sieve, special number field sieve},
  cr_date = {1990-12-31},
  cr_date_precision = {year},
  cr_status = {published},
  cr_venue = {STOC 1990},
  cr_author_ids = {arjen-k-lenstra; hendrik-w-lenstra-jr; mark-s-manasse; john-m-pollard}
}