Faster deterministic integer factorization

(with Edgar Costa)

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

arXiv preprint (January 2012).


The best known unconditional deterministic complexity bound for computing the prime factorization of an integer N is O(Mint(N1/4 log N)), where Mint(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