求一个大素数的生成元代码
时间: 2024-05-16 13:15:39 浏览: 8
以下是使用Python语言生成大素数及其生成元的代码:
```python
import random
import math
def is_prime(n):
if n < 2:
return False
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
return False
return True
def generate_prime_number(bits):
while True:
p = random.getrandbits(bits)
if is_prime(p):
return p
def generate_primitive_root(p):
factors = []
phi = p - 1
n = phi
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
factors.append(i)
while n % i == 0:
n //= i
if n > 1:
factors.append(n)
for g in range(2, p):
flag = True
for factor in factors:
if pow(g, phi // factor, p) == 1:
flag = False
break
if flag:
return g
p = generate_prime_number(1024)
g = generate_primitive_root(p)
print("p =", p)
print("g =", g)
```
这里使用了Miller-Rabin素性检验法来判断一个数是否为素数。同时,使用了一个算法来生成指定素数的生成元。请注意,随着p位数的增加,计算时间会变得越来越长。