尝试大值时整数溢出 - 因式分解算法

Question

我尝试实现费马的分解方法（参见https://en.wikipedia.org/wiki/Fermat%27s_factorization_method），代码如下：

import math
def is_square(apositiveint):
  x = apositiveint // 2
  seen = set([x])
  while x * x != apositiveint:
    x = (x + (apositiveint // x)) // 2
    if x in seen: return False
    seen.add(x)
  return True

def fermat(n):
    a = math.ceil(math.sqrt(int(n)))
    b2 = a*a - n
    while not is_square(b2):
        a = a+1
        b2 = a*a - n
    return (a-math.sqrt(b2))

所以我的目标是分解整数 n。为此，我定义了另外两个变量： a 定义为 n 的四舍五入平方根，b 是平方和我要分解的数字之间的差值。

while 循环表示，如果 b2 不是正方形，则递增 a 并将 b2 定义为新 a 的平方与我要分解的数字之间的差值。如果 b2 是平方，则 b2 的平方根将是一个因数。

当我像这样调用函数 print(fermat(133)) 时，问题运行良好，它给出了答案 7，因为它是最低的质因数，然后我只需要将 133 除以 7 就得到 19。到目前为止太好了

但我想使用此代码破解我必须分解的 Rsa 密码系统

n = 507204827540547635003188460612372848602900324231921153214257357007181658245923199433998982097775501221867848469443624920597607769543938674944505236183262115817470130367565835690961161034764686003873284004530093885216278169686899261491680377671371989819332490227245364291020052993400797298847667351869225677060848581769823704347697557065010283805595504356259635995676212493990051132738242918342267376701

但是由于 n 太大，我得到一个溢出错误，当然，它说 "int too large to convert to float"。

这个错误让我做了一些研究，我发现 from decimal import Decimal。由于我是编程新手，所以我尝试在函数 fermat(n) 的任何地方实现它，如下所示：

def fermat(n):
        a = Decimal(math.ceil(math.sqrt(int(n))))
        b2 = Decimal(a*a - n)
        while not is_square(b2):
            a = Decimal(a+1)
            b2 = Decimal(a*a - n)
        return (Decimal(a-math.sqrt(b2)))

但是，在那之后，我仍然遇到完全相同的问题。我真的不明白 "Decimal" 应该做什么，尽管在阅读之后。知道我可以做些什么来使此代码适用于大 n 吗？

我确定我忘了分享一些我认为很重要的信息。但是一时想不起来是什么了。如果我忘记了什么，我会稍后更新。希望有人能帮助我，谢谢:)

Answer 1

您需要将计算的最大值重新定义为运行。看看

import sys
sys.maxsize

你会看到这个数字比你的 n 值小得多。在你的情况下，我建议不要使用数学库，而使用你自己的实现。

math.ceil() returns 一个浮点数，它不适合你的长整数。

尝试大值时整数溢出 - 因式分解算法

Integeroverflow when trying large values - factorization algorithm

python

python-3.x

rsa

integer-overflow