分解30位十进制数字的算法
分解30位十进制数字的算法
提问于 2020-04-07 12:35:15
我的教授给了我一个RSA因子分解问题的作业。给定的模数是30位十进制数。我已经搜索了很多关于因子分解算法的内容。但是为我给定的需求选择一个是相当令人头疼的。对于30位十进制数字，哪种算法的性能更好？
注意:到目前为止，我已经读到了关于蛮力方法和二次筛子的文章。后者很复杂，前者很耗时。
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-04-07 15:54:55
还有另一种称为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或者，您可以只使用现有的软件库。我看不出重新发明这个轮子有多大意义。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/61072905
复制相关文章
相似问题
腾讯云开发者
