我正在尝试使用Fermat的因式分解方法http://en.wikipedia.org/wiki/Fermat%27s_factorization_method来进行RSA演算n = pq = 17113393402958118715148546526344227921781458985077442510282855190555424972779474416264134494113
这是我的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
s,这是不正确的。我认为这是python中的截断错误。我应该如何处理?谢谢。
def isqrt(n):
x = n
y = (x + n // x) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x
print isqrt(99999999999**2)
for i in xrange(130000,140000):
if isqrt(n + i*i) ** 2 == n + i*i:
print isqrt(n + i*i)
print "done"
math.sqrt使用不精确的浮点数。
最简单的方法可能是将sqrt更改为整数isqrt函数,您可以仅从https://stackoverflow.com/a/15391420/220700复制体面的isqrt实现
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句