A deterministic algorithm for finding \(r\)-power divisors (Q2093686): Difference between revisions

In this paper under review the author provides a deterministic algorithm, where on input a positive integer \(N\), outputs all the positive integers \(d\) such that \(d^r|N,\) \(r\) positive integer. If we assume that \(r\ll \log_2{N},\) then the running time, in bit operations, is \(O\bigg(N^{1/4r}\frac{(\log_2{N})^{10+\varepsilon}}{r^3}\bigg), \) for any \(\varepsilon>0.\) The author remarks that, the algorithm is impractical for small \(r\), so it can not compete the general-purpose factorization algorithms. It is important to notice that, the algorithm is \textit{fully} deterministic, whereas in other factorization algorithms such as ECM and NFS, the algorithms are based on heuristic assumptions in order to be analyzed with respect to their running time. If we apply the algorithm of the paper in the squarefreeness problem of an integer \(N,\) the best algorithms have running time \(O(N^{1/6 +\varepsilon}) \), however the algorithm of the paper provides running time \(O(N^{1/8+\varepsilon}).\) As far as the case \(r=1\), the algorithm does not provide any improvement from the Coppersmith's algorithm, i.e. the running time remains \(O(N^{1/4+\varepsilon}).\) The proof of the Theorem builds on the work of Boneh, Durfee and Howgrave-Graham.