A deterministic algorithm for finding $r$-power divisors

Abstract

Building on work of Boneh, Durfee and Howgrave-Graham, we present a deterministic algorithm that provably finds all integers $p$ such that $p^r|N$ in time $O(N^{1/4r+\hat{I}\mu })$ for any $\hat{I}\mu >0$. For example, the algorithm can be used to test squarefreeness of $N$ in time $O(N^{1/8+\hat{I}\mu })$; previously, the best rigorous bound for this problem was $O(N^{1/6+\hat{I}\mu })$, achieved via the Pollard--Strassen method.

16 pages