(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.