费马因子分解python

费马因子分解是一种简单的分解正整数的方法，但对于大数来说不够高效。下面是一个简单的Python实现，适用于小于100位的正整数。

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
    return int(a + math.sqrt(b2)), int(a - math.sqrt(b2))

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

在上述代码中，函数`fermat_factorization(n)`接受一个正整数n作为输入，返回n的两个因子p和q。具体实现过程如下：

1. 取a = ceil(sqrt(n))，即向上取整的n开根号的整数部分。
2. 计算b2 = a^2 - n。
3. 如果b2是完全平方数，则返回`int(a + sqrt(b2))`和`int(a - sqrt(b2))`，即n的两个因子。
4. 否则，令a = a + 1，重复步骤2和3，直到找到n的因子为止。

需要注意的是，这种算法仅适用于小于100位的正整数，并且不能保证总是能够找到整数n的因子。因此，在实际应用中，需要使用更高效的因数分解算法，例如Pollard-Rho算法、Quadratic Sieve算法等。