A time-space tradeoff for Lehman's deterministic integer factorization method

Markus Hittmeir

Mathematics of Computation 2021

Time bound

N^2/9+o(1) bit operations

Space bound

Not extracted from the source

Source / version date

30 Jun 2020

Comparison variant

General integers · proven deterministic

Cost scale

N^c+o(1)

coefficientExact

2/9

Assumptions and source notes

Unconditional deterministic improvement using a time-space tradeoff for a generalization of Lehman’s method.

Source location

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

Primary source ↗

@misc{hittmeir20,
  author = {Markus Hittmeir},
  title = {{A time-space tradeoff for Lehman's deterministic integer factorization method}},
  journal = {Mathematics of Computation 90, 1999–2010},
  year = {2021},
  doi = {10.1090/mcom/3623},
  url = {https://arxiv.org/abs/2006.16729},
  keywords = {factoring, deterministic, time-space tradeoff},
  cr_date = {2020-06-30},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Mathematics of Computation 90, 1999–2010},
  cr_author_ids = {markus-hittmeir}
}