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

Question

我尝试实现 Fermat 的分解方法(参见 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 是 a 的平方和我要分解的数字之间的差。

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

当我调用这样的函数时，问题就很好解决 print(fermat(133)) 它给了我答案 7，因为它是最低的质因数，然后我只需将 133 除以7 到 19。到目前为止一切顺利。

但是我想使用这段代码来破解 Rsa 密码系统，我必须考虑因素

n = 507204827540547635003188460612372848602900324231921153214257357007181658245923199433998982097775501221867848469443624920597607769543938674944505236183262115817470130367565835690961161034764686003873284004530093885216278169686899261491680377671371989819332490227245364291020052993400797298847667351869225677060848581769823704347697557065010283805595504356259635995676212493990051132738242918342267376701

但是，由于 n 太大，我当然会遇到溢出错误，其中显示“int 太大，无法转换为 float”。

这个错误让我做了一些研究，我发现fromdecimalimportDecimal。由于我对编程还很陌生，因此我尝试在函数 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)))

但是，在那之后，我仍然遇到同样的问题。不过，在阅读完“十进制”之后，我真的不明白“十进制”应该做什么。知道我可以做什么来让这段代码适用于大 n 吗？

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

Answer 1

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

import sys
sys.maxsize 

你会发现这个数字比你的 n 值小得多。对于您的情况，我建议不要使用数学库，并使用您自己的实现。

ma​​th.ceil() 返回一个 float ，它不适合您的长整数。