Fermat 分解法

  • 目标： 在仅知 $hint=p⋅q\text{hint} = p \cdot q $的情况下，分解出 pp 和 qq。
  • 适用条件： 当两个因子接近时（本题中 $q≈p+2400q \approx p + 2^{400}$，相对 $hint\text{hint} $的量级仍算接近），Fermat 分解法很有效。
  • 思想： 设

$p=a−b,q=a+b$

则

$\text{hint} = p \cdot q = (a - b)(a + b) = a^2 - b^2$

只要找到最小的整数 $a≥[\sqrt{hint}]$，使得 $$a^2 - \text{hint}$$是完全平方数，即 $b^2$。这时 $b = \sqrt{a^2 - \text{hint}}$，得到 $p, q$。

  • 实现要点：
    • 起点选择： 从 $a = \lceil\sqrt{\text{hint}}\rceil $开始。
    • 迭代检查： 每次计算 $b^2 = a^2 - \text{hint}$，判断是否为完全平方数。若是，则返回 $p = a - b、q = a + b$。
    • 素性验证： 用素数判定确认p, q 均为素数。如果初次返回的两个数中不是按素性期望排列，则交换保证 p, q 的语义一致。
  • 意义： 在不需要枚举巨大偏移量的情况下，快速从 hint 恢复 p,q。
1
2
3
4
5
6
7
8
9
10
def fermat_factor(N):
    a = isqrt(N)
    if a * a < N:
        a += 1
    while True:
        b2 = a * a - N
        b = isqrt(b2)
        if b * b == b2:
            return int(a - b), int(a + b)
        a += 1