费马因子分解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.sqrt(b2)
    q = a - math.sqrt(b2)
    return int(p), int(q)

n = 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145

p, q = fermat_factorization(n)
print("p = ", p)
print("q = ", q)

在这个示例中，输入的大质数为n，程序通过费马因子分解的方法寻找其质因数p和q，并输出结果。