在python中获取平方根时发生截断错误

Question

我正在尝试使用Fermat的因子分解方法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中的截断错误。我该如何处理？谢谢

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"

Answer 1

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

最简单的方法可能是将sqrt更改为integer isqrt函数，您只需从https://stackoverflow.com/a/15391420/220700

Answer 2

您可以使用牛顿方法来找到一个数字的整数平方根：

def isqrt(n):
    x = n
    y = (x + n // x) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

这将返回最大整数x，使得x×x不超过n。

但Fermat的方法不太可能对95位RSA半素数进行因子分解。你应该看看二次筛或数字域筛来计算这个大小的数字。

Answer 3

您可以尝试在模块数学之外使用sqrt（）函数。代码可能看起来像：

import math
n = math.sqrt(int(raw_input("Enter a numbern")))
print n