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

Question

我试着用费马的因式分解法 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中的截断错误。我该怎么处理？谢谢。在

^{pr2}$

Answer 1

您可以使用牛顿法求一个数的整数平方根：

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。在

但费马的方法不太可能计算出你的95位RSA半素数。你应该看看二次筛或数字字段筛来计算这个大小的数字。在