IFP / General integers · 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, 3^2/3]
Space bound: Not extracted from the source

Source / version date: 1990
Comparison variant: General integers · heuristic · L(1/3)
Cost scale: L_N[1/3,c]
coefficientExact: 3^{2/3}

Assumptions and source notes

The 1990 work-in-progress paper describes the proposed generalization to arbitrary integers with this heuristic constant. It is an early general-purpose bound, not the special-form 1.526 bound.

Source location

Introduction, second page; generalized algorithm discussion
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}
}