时间复杂度为 O(2^(n/2)) 的整数分解算法的效率如何?

Question

与其他因式分解算法相比，具有时间复杂度O(2^(n/2))的n位数字的整数分解算法的效率如何？

Answer 1

是的，检查区间[1..sqrt(X)]的所有除数的简单算法具有相同的复杂性O(2^(n/2))。

波拉德的rho算法具有复杂性O(2^(n/4))。这个是旧算法，易于实现，适用于不是很长的整数。

但现代数论有更有效的算法，例如通用数场筛或波拉德-斯特拉森算法。

您可以在wiki列表中阅读有关已知流行分解算法的更多信息