费马因子分解python

费马因子分解是一种用于分解大质数的算法，可以用Python实现。以下是一个简单的实现示例：

import math

def fermat_factorization(n):
    a = math.ceil(math.sqrt(n))
    b2 = a*a - n
    while not math.sqrt(b2).is_integer():
        a += 1
        b2 = a*a - n
    p = a + math.isqrt(b2)
    q = a - math.isqrt(b2)
    return p, q

# 示例用法
n = 851
p, q = fermat_factorization(n)
print(f"{n}的质因数分解结果为: {p} * {q}")

这个实现使用费马方法，使用a作为初始值，计算b2 = a^2 - n，如果b2是平方数，那么p = a + sqrt(b2)和q = a - sqrt(b2)就是n的两个因子。