论文标题
用于查找$ r $ $ - 权力除数的确定性算法
A deterministic algorithm for finding $r$-power divisors
论文作者
论文摘要
在Boneh，Durfee和Howgrave-Graham的作品的基础上，我们提出了一种确定性算法，可证明所有整数$ p $，因此$ p^r \ mathrel | n $ in Time $ O（N^{1/4R+ε}）$对于任何$ε> 0 $。例如，该算法可用于测试时间$ o（n^{1/8+ε}）$的$ n $ in $ n $; n $ n $;以前，通过Pollard-Strassen方法实现的最佳严格限制是$ O（N^{1/6+ε}）$。
Building on work of Boneh, Durfee and Howgrave-Graham, we present a deterministic algorithm that provably finds all integers $p$ such that $p^r \mathrel| N$ in time $O(N^{1/4r+ε})$ for any $ε> 0$. For example, the algorithm can be used to test squarefreeness of $N$ in time $O(N^{1/8+ε})$; previously, the best rigorous bound for this problem was $O(N^{1/6+ε})$, achieved via the Pollard--Strassen method.
