IFP / General integers · proven deterministic

An exponent one-fifth algorithm for deterministic integer factorisation

David Harvey

Mathematics of Computation 2021

PublishedSource checked

Time bound: N^1/5+o(1) bit operations
Space bound: Not extracted from the source

Source / version date: 12 Oct 2020
Comparison variant: General integers · proven deterministic
Cost scale: N^c+o(1)
coefficientExact: 1/5

Assumptions and source notes

Unconditional deterministic complete factorization. This exponent is in N, so it is exponential in the input bitlength.

Source location

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

Primary source ↗

BibTeXDownload .bib

@misc{harvey20,
  author = {David Harvey},
  title = {{An exponent one-fifth algorithm for deterministic integer factorisation}},
  journal = {Mathematics of Computation 90, 2937–2950},
  year = {2021},
  doi = {10.1090/mcom/3658},
  url = {https://arxiv.org/abs/2010.05450},
  keywords = {factoring, deterministic},
  cr_date = {2020-10-12},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Mathematics of Computation 90, 2937–2950},
  cr_author_ids = {david-harvey}
}