我试着用费马的因式分解法
http://en.wikipedia.org/wiki/Fermat%27s_factorization_method
使用n = pq = 17113393402958118715148546526344227921781458985077442510282855190555424972779474416264134494113
来计算RSA练习
下面是我的python代码:
def isSquare(x):
return pow(int(sqrt(x)),2) - x == 0
n = 17113393402958118715148546526344227921781458985077442510282855190555424972779474416264134494113
for i in xrange(10):
print isSquare(n+i*i)
当我执行时,它打印所有的True
,这是不正确的。我认为这是python中的截断错误。我该怎么处理?谢谢。在
您可以尝试在模块math之外使用sqrt()函数。代码可能看起来像:
在数学.sqrt使用浮点数,这是不精确的。在
最简单的方法可能是将sqrt更改为integer isqrt函数,您只需从https://stackoverflow.com/a/15391420/220700复制像样的isqrt实现即可
您可以使用牛顿法求一个数的整数平方根:
这将返回最大的整数x,使得x×x不超过n。在
但费马的方法不太可能计算出你的95位RSA半素数。你应该看看二次筛或数字字段筛来计算这个大小的数字。在
相关问题 更多 >
编程相关推荐