# Faster deterministic integer factorization

(with Edgar Costa)

Math. Comp. **83** (2014), 339–345 (DOI).

arXiv preprint (January 2012).

## Abstract

The best known unconditional deterministic complexity bound for computing the prime factorization of an integer *N* is *O*(M_{int}(*N*^{1/4} log *N*)), where M_{int}(*k*) denotes the cost of multiplying *k*-bit integers. This result is due to Bostan–Gaudry–Schost, following the Pollard–Strassen approach. We show that this bound can be improved by a factor of (log log *N*)^{1/2}.

Back to the main page