一个简单的确定性的无用的质因子分解算法

假设 $N$ 是合数，那么有一个不超过 $N^{1/2}$ 的素因子。 我们令 $B=\lfloor N^{1/4}\rfloor$，使用**快速阶乘算法**求出 $B$ 阶下降幂在 $B, 2B, \dots, B^2$ 处 $\bmod N$ 的点值，虽然我们现在不知道 $N$ 是不是质数，但是如果快速阶乘算法调用过程中调用的整数求逆如果做不了，自然就成功分解出了一个非平凡因子。最后，我们把每个点值和 $N$ 取 $\gcd$，如果不是质数那么也一定能确定一个长为 $N^{1/4}$ 的区间，然后依个枚举即可找到一个质因子。 由此，我们就得到了一个 $O(N^{1/4}\log N)$ 分解质因数的**确定性**算法。当然这个算法除了理论意义上是确定性以外好像没啥用。 注 1：本文是随机翻阅 Algorithmes Efficaces en Calcul Formel 的时候看到的。 注 2：截止本文发表，质因子分解的确定性算法的最优复杂度似乎[是](https://arxiv.org/abs/2105.11105)： $$ O\left(\frac{N^{1/5}\log^{16/5}N}{(\log\log N)^{3/5}}\right) $$