费马因式分解算法对大梅森素数失效？代码是否有误？

你的代码存在错误，并非费马因式分解算法对大素数失效。

错误原因 #

费马因式分解的核心是将N表示为a² - b² = (a-b)(a+b)，对于素数N，它的唯一分解是1 × N，算法本身是有效的。但你的代码中判断b_square是否为完全平方数的方式有问题：
使用math.sqrt(b_square).is_integer()依赖浮点数运算，而浮点数的精度有限，当处理极大数时，无法精确表示超大整数的平方根，会导致误判——把非完全平方数错误识别为完全平方数，提前退出循环，返回错误的因子。

比如测试2147483647这个素数时，循环中某个a对应的a² - N并非完全平方数，但math.sqrt返回的近似浮点数被is_integer()判定为整数，最终计算出错误的b，得到268435456 × 8的错误结果。

修正后的代码 #

将判断完全平方数的逻辑改为用整数运算验证，避免浮点数精度问题：

import math

N = int(input("Insert a large number: "))

def fermat_factorization(N: int) -> list[int]:
    if N % 2 == 0:
        return [2, N // 2]

    a = math.isqrt(N) + 1
    b_square = a**2 - N

    while True:
        b = math.isqrt(b_square)
        if b * b == b_square:
            break
        a += 1
        b_square = a**2 - N

    return [a + b, a - b]

factors = fermat_factorization(N)
print(f"\nThe factors of {N} are {factors}")

效果说明 #

修正后的代码会正确处理素数：对于素数N，最终会找到a=(N+1)//2，b=(N-1)//2，返回[N, 1]（或顺序相反），符合素数的分解结果。

内容的提问来源于stack exchange，提问作者lanzik03