使用python求解一个数的原根

要求一个数g是模n的原根，需要满足以下条件：

1. g^(phi(n)) ≡ 1 (mod n)
2. 对于n的任意质因数p，都满足g^(phi(n)/p) ≢ 1 (mod n)

其中，phi(n)表示欧拉函数，即小于n且与n互质的正整数个数。

下面是使用python求解一个数的原根的代码：

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

def is_primitive_root(g, n):
    if gcd(g, n) != 1:
        return False
    phi_value = phi(n)
    factors = factorize(phi_value)
    for p in factors:
        if pow(g, phi_value // p, n) == 1:
            return False
    return True

def primitive_root(n):
    phi_value = phi(n)
    for g in range(2, n):
        if is_primitive_root(g, n):
            return g
    return None

其中，gcd表示求最大公约数的函数，factorize表示对数进行因数分解的函数，可以自行实现。

通过调用primitive_root函数，即可求解一个数的原根。