IFP / General integers · heuristic · L(1/3)

Factoring integers with the number field sieve

Joe P. Buhler · Hendrik W. Lenstra Jr. · Carl Pomerance

The Development of the Number Field Sieve 1993

PublishedSource checked

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

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

Assumptions and source notes

The general number field sieve has this predicted expected running time under smoothness and related heuristic assumptions. It is not a rigorous worst-case theorem.

Source location

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

Primary source ↗

BibTeXDownload .bib

@incollection{blp93,
  author = {Joe P. Buhler and Hendrik W. Lenstra Jr. and Carl Pomerance},
  title = {{Factoring integers with the number field sieve}},
  booktitle = {The Development of the Number Field Sieve},
  year = {1993},
  doi = {10.1007/BFb0091539},
  url = {https://doi.org/10.1007/BFb0091539},
  keywords = {factoring, general number field sieve},
  cr_date = {1993-12-31},
  cr_date_precision = {year},
  cr_status = {published},
  cr_venue = {The Development of the Number Field Sieve},
  cr_author_ids = {joe-p-buhler; hendrik-w-lenstra-jr; carl-pomerance}
}