IFP / General integers · proven randomized · L(1/2)

A rigorous time bound for factoring integers

Hendrik W. Lenstra Jr. · Carl Pomerance

Journal of the American Mathematical Society 1992

PublishedSource checked

Time bound: L_N[1/2, 1]
Space bound: Not extracted from the source

Source / version date: Jul 1992
Comparison variant: General integers · proven randomized · L(1/2)
Cost scale: L_N[1/2,c]

Assumptions and source notes

Unconditional randomized expected-time theorem for complete prime factorization. This must be kept apart from deterministic bounds and heuristic smoothness analyses.

Source location

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

Primary source ↗

BibTeXDownload .bib

@article{lp92,
  author = {Hendrik W. Lenstra Jr. and Carl Pomerance},
  title = {{A rigorous time bound for factoring integers}},
  journal = {Journal of the American Mathematical Society 5(3), 483–516},
  year = {1992},
  doi = {10.1090/S0894-0347-1992-1137100-0},
  url = {https://doi.org/10.1090/S0894-0347-1992-1137100-0},
  keywords = {factoring, class groups, unconditional, randomized},
  cr_date = {1992-07-31},
  cr_date_precision = {month},
  cr_status = {published},
  cr_venue = {Journal of the American Mathematical Society 5(3), 483–516},
  cr_author_ids = {hendrik-w-lenstra-jr; carl-pomerance}
}