分解 30 位十进制数字的算法

Question

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

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

Answer 1

还有另一种方法称为 Pollard's Rho algorithm，它不如 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 == n:
        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

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

分解 30 位十进制数字的算法

Algorithms for factorizing a 30 decimal digit number

cryptography

prime-factoring

factorization