二次筛法分解大整数代码

二次筛法，也被称为Pollard rho算法，是一种用于分解大整数的素因数分解算法。它基于费马小定理，通过随机化的过程寻找合数的因子。以下是基本的代码框架：

def gcd(a, b):
    # 计算最大公约数
    while b != 0:
        a, b = b, a % b
    return a

def fermat_test(n, base=2):
    # 检查是否满足费马小定理
    if pow(base, n - 1, n) != 1:
        return False
    return True

def rho_factorization(n):
    x = y = random.randint(1, n - 1)
    d = 1

    def iteration():
        nonlocal x, y, d
        y = (y * y + 1) % n
        delta = gcd(abs(x - y), n)
        if delta > 1 and delta != d:
            d = delta
            return d
        x = y

    while True:
        factor = iteration()
        if factor != 1:
            return factor

# 示例
n = int(input("请输入一个大整数: "))
factor = rho_factorization(n)
print(f"分解结果: {factor}")