使用素性检测(如Miller-Rabin)算法生成大素数,写一个python代码
时间: 2023-12-29 07:02:23 浏览: 70
好的,以下是使用Miller-Rabin算法生成大素数的Python代码:
```python
import random
def is_prime(n, k=5):
if n < 2:
return False
if n == 2 or n == 3:
return True
if not n & 1:
return False
r, d = 0, n-1
while d % 2 == 0:
r += 1
d //= 2
for _ in range(k):
a = random.randint(2, n-2)
x = pow(a, d, n)
if x == 1 or x == n-1:
continue
for _ in range(r-1):
x = pow(x, 2, n)
if x == n-1:
break
else:
return False
return True
def generate_prime(n):
while True:
p = random.randint(2**(n-1), 2**n-1)
if is_prime(p):
return p
```
其中,`is_prime(n,k)`函数用于判断一个数n是否为素数,k为循环次数,可根据需要调整;`generate_prime(n)`函数用于生成一个n位的大素数。
阅读全文