IFP / General integers · proven deterministic

Faster deterministic integer factorization

Edgar Costa · David Harvey

Mathematics of Computation 2014

PublishedSource checked

Time bound: O(M_int(N^1/4 log N) / sqrt(log log N))
Space bound: Not extracted from the source

Source / version date: 10 Jan 2012
Comparison variant: General integers · proven deterministic
Cost scale: N^c+o(1)
coefficientExact: 1/4

Assumptions and source notes

The exact improvement is a sqrt(log log N) factor over the Bostan–Gaudry–Schost bound. The normalized exponent is still 1/4. M_int(k) denotes k-bit integer multiplication cost.

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{ch12,
  author = {Edgar Costa and David Harvey},
  title = {{Faster deterministic integer factorization}},
  journal = {Mathematics of Computation 83, 339–345},
  year = {2014},
  doi = {10.1090/S0025-5718-2013-02707-X},
  url = {https://arxiv.org/abs/1201.2116},
  keywords = {factoring, deterministic},
  cr_date = {2012-01-10},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Mathematics of Computation 83, 339–345},
  cr_author_ids = {edgar-costa; david-harvey}
}