分解 30 位十进制数的算法

Question

我的教授给了我一个 RSA 因式分解问题。给定的模数是 30 个十进制数字长。我一直在搜索很多关于因式分解算法的信息。但是对于我给定的要求，选择一个是一件很头疼的事情。对于 30 位十进制数字，哪些所有算法都能提供更好的性能？

注意：到目前为止，我已经阅读了蛮力法和二次筛法。后者复杂，前者耗时。

Answer 1

还有另一种方法称为 Pollard 的 Rho 算法，它不如 GNFS 快，但能够在几分钟而不是几小时内分解 30 位数字。

算法非常简单。它会在找到任何因子时停止，因此您需要递归调用它以获得完整的因式分解。这是 Python 中的基本实现：

def rho(n):
    def gcd(a, b):
        while b > 0:
            a, b = b, a%b
        return a
    g = lambda z: (z**2 + 1) % n
    x, y, d = 2, 2, 1
    while d == 1:
        x = g(x)
        y = g(g(y))
        d = gcd(abs(x-y), n)
    if d == 0:
        print("Can't factor this, sorry.")
        print("Try a different polynomial for g(), maybe?")
    else:
        print("%d = %d * %d" % (n, d, n // d))

rho(441693463910910230162813378557) # = 763728550191017 * 578338290221621

或者您可以只使用现有的软件库。我看不出重新发明这个特殊的轮子有多大意义。