Faster deterministic integer factorization
Edgar Costa, David Harvey · Mathematics of Computation · 2013
The best known unconditional deterministic complexity bound for computing the prime factorization of an integer N N is O ( M i n t ( N 1 / 4 log N ) ) O(\mathsf {M}_{\mathrm {int}}(N^{1/4} \log N)) , where M i n t ( k ) \mathsf {M}_{\mathrm {int}}(k) denotes the cost of multiplying k k -bit integers. This result is due to Bostan, Gaudry, and Schost, following the Pollard–Strassen approach. We show that this bound can be improved by a factor of log log N \sqrt {\log \log N} .