我的教授给了我一个RSA因数分配问题。给定的模数为30个十进制数字长。我一直在搜索很多关于分解算法的文章。但是，为我给定的要求选择一个一直很头疼。哪些算法对30个十进制数字的性能更好？
注意：到目前为止，我已经阅读了有关蛮力法和二次筛的信息。后者很复杂，前者很费时。
还有另一种称为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 == 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
或者，您可以只使用现有的软件库。重新发明这个特殊的轮子我看不出什么意义。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句