python实现求一个大数2020020010510000000000000000000000000000000000000000000000000000000000000000000043的原根

下面是一个Python实现，使用了上述方法来计算模数的原根:

from math import gcd
from functools import reduce

def phi(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

def inv_mod(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise ValueError('modular inverse does not exist')
    else:
        return x % m

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def find_primitive_root(n):
    factors = factorize(n)
    phi_n = phi(n)
    for g in range(2, n):
        if gcd(g, n) > 1:
            continue
        if pow(g, phi_n, n) != 1:
            continue
        if all(pow(g, phi_n // p, n) != 1 for p in factors):
            return g
    raise ValueError('no primitive root found')

def factorize(n):
    factors = []
    p = 2
    while p * p <= n:
        if n % p == 0:
            factors.append(p)
            while n % p == 0:
                n //= p
        p += 1
    if n > 1:
        factors.append(n)
    return factors

def chinese_remainder_theorem(a, m):
    M = reduce(lambda x, y: x * y, m)
    x = sum(ai * Mi * inv_mod(Mi, mi) for ai, mi, Mi in zip(a, m, (M // mi for mi in m)))
    return x % M

n = 2020020010510000000000000000000000000000000000000000000000000000000000000000000000043
factors = factorize(n)
phis = [phi(p) for p in factors]
g_mod_p = [find_primitive_root(p) for p in factors]
gcds = [gcd(p1, p2) for i, p1 in enumerate(factors) for p2 in factors[i+1:]]
assert all(gcd(g, n) == 1 for g in g_mod_p)
assert all(pow(g, phi_n // p, p) != 1 for g, p in zip(g_mod_p, factors) for q in factors if p % q == 0)
assert all(gcd(g, m // p) == 1 for i, p in enumerate(factors) for g in g_mod_p[:i] + g_mod_p[i+1:] for m in factors if m % p == 0)
g = chinese_remainder_theorem(g_mod_p, factors)
print(g)

该代码首先使用`factorize`函数将模数分解为质因子，然后使用`phi`函数计算每个质因子的欧拉函数值。然后，对于每个质因子，使用`find_primitive_root`函数找到一个原根，并确保原根满足条件。最后，使用`chinese_remainder_theorem`函数合并原根，得到整个模数的原根。