python 求阶数 原根

Python中求解阶数和原根的方法如下：

1. 首先，我们可以使用欧拉函数φ(p)来求解阶数。阶数是φ(p)，遍历2到p，检验阶数是否等于φ(p)=p-1即可。具体实现时，可以使用循环遍历2到p，对每一个数n，计算n的阶，并检查是否等于p-1。如果等于，则n是原根。

2. 另外，对于p-1的素因子的求解，可以使用yafu工具进行分解。首先，安装yafu工具，并使用循环调用该工具来分解p-1。然后，对于每一个素因子i，检查n的(i-1)次方是否等于1 (mod p)。如果不等于1，则n是原根。

下面是一个示例代码，展示了如何使用Python来求解阶数和原根：

from sympy import is_primitive_root, primerange

def find_primitive_root(p):
    for n in range(2, p):
        if is_primitive_root(n, p):
            return n
    return None

def find_prime_factors(n):
    factors = []
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def find_primitive_root_yafu(p):
    factors = find_prime_factors(p-1)
    for i in factors:
        power = (p-1) // i
        if pow(n, power, p) != 1:
            return False
    return True

p = 31
primitive_root = find_primitive_root(p)
print("原根:", primitive_root)

阶数 = p - 1
print("阶数:", 阶数)