求大素数原根方法python
时间: 2023-12-14 08:31:17 浏览: 76
要求一个大素数的原根,可以使用求最小原根的方法。具体步骤如下:
1. 首先,将大素数p-1分解质因数,得到p-1=q1^k1 * q2^k2 * ... * qm^km,其中q1,q2,...,qm为不同的质数。
2. 对于每个质因子qi,求出它的一个原根gqi。
3. 对于每个质因子qi,求出p-1关于qi的阶dqi,即dqi是最小的正整数,使得gqi^dqi ≡ 1 (mod p)。
4. 对于每个质因子qi,求出tqi=dqi/kqi,其中kqi=q1^k1 * q2^k2 * ... * qm^km / qi^ki。
5. 对于每个质因子qi,将gqi^(tqi) mod p作为候选的原根。
6. 验证每个候选原根是否满足g^((p-1)/qi)≠1 (mod p)。
7. 如果有满足条件的候选原根,则它就是p的一个原根;否则,p没有原根。
下面是一个Python代码实现:
```
def is_primitive_root(g, p):
factors = factor(p - 1)
for q, _ in factors:
if pow(g, (p - 1) // q, p) == 1:
return False
return True
def primitive_root(p):
factors = factor(p - 1)
for g in range(2, p):
if all(pow(g, (p - 1) // q, p) != 1 for q, _ in factors):
return g
return None
```
其中,factor(n)是一个函数,用于分解n的质因数。