在python中取平方根的截断错误

用户名

我正在尝试使用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)

当我执行时,它会打印出所有Trues,这是不正确的。我认为这是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"
塞尔吉·迪姆琴科(Sergii Dymchenko)

math.sqrt使用不精确的浮点数。

最简单的方法可能是将sqrt更改为整数isqrt函数,您可以仅从https://stackoverflow.com/a/15391420/220700复制体面的isqrt实现

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章