A log-log speedup for exponent one-fifth deterministic integer factorisation

David Harvey · Markus Hittmeir

Mathematics of Computation 2022

Time bound

O(N^1/5 (log N)^16/5 / (log log N)^3/5) bit operations

Space bound

Not extracted from the source

Source / version date

24 May 2021

Comparison variant

General integers · proven deterministic

Cost scale

N^c+o(1)

coefficientExact

1/5

Assumptions and source notes

Same leading exponent 1/5; improves the logarithmic factors. This should appear as a tied leading exponent rather than an artificial exponent improvement.

Source location

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

Primary source ↗

@misc{hh21,
  author = {David Harvey and Markus Hittmeir},
  title = {{A log-log speedup for exponent one-fifth deterministic integer factorisation}},
  journal = {Mathematics of Computation 91, 1367–1379},
  year = {2022},
  doi = {10.1090/mcom/3708},
  url = {https://arxiv.org/abs/2105.11105},
  keywords = {factoring, deterministic},
  cr_date = {2021-05-24},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Mathematics of Computation 91, 1367–1379},
  cr_author_ids = {david-harvey; markus-hittmeir}
}