费马分解

在RSA密码中，当我们需要解密但没有 p 和 q 时是很难解出 ɸ(n) = ( p - 1 ) * ( q - 1 ) 的，这时候就需要我们将 n 分解为 p 和 q ，但是大质数分解是十分困难的，这时候可以使用费马分解法分解出 p 和 q 。

但是费马分解法使用时有一定的要求

在 p 和 q 相差不是很大的情况下可以使用费马分解。

费马分解的核心就是存在两个相差不大的素数的乘积，可以通过构造完全平方差的方式求出这两个素数。

n = p * q ( p 和 q 为两个质数 ，n 为 p 和 q 的乘积 )

已知 n ，并且 p 和 q 的大小相差不大。

构造完全平方差公式

n = p q = ( s - t ) ( s + t ) = s ² - t ²

使得 n 为两数的平方差 ，然后变换得

t ² = s ² - n

令 s = int ( sqrt ( n ) ) + 1 ，

当 s 满足上式时则表明找到了符合条件的 s 和 t ，

否则 s + 1 继续判断是否符合上式要求，直至找到满足要求的 s 和 t 。

找到满足上式要求的 s 和 t 后，只需 带入第一个式子中求出对应的 p 和 q ，即 p , q = s ± t

Python代码实现

import math
def fermat(n):    # 费马分解
    s = int(math.isqrt(n))+1    # 构造 s
    t = pow(s,2) - n        # 构造 t
    while int(math.isqrt(t)) != math.isqrt(t): # 判断 t 和 s 是否为完全平方差，不是则继续判断
        s+=1    
        t=pow(s,2) - n
    t = int(math.isqrt(t))
    p = s - t
    q = s + t
    return p,q
res = fermat(n)
print(res)