python实现素性检测(如Miller-Rabin)算法生成大素数。
时间: 2023-12-31 10:05:36 浏览: 126
下面是使用 Miller-Rabin 算法生成大素数的 Python 代码:
```python
import random
def is_prime(n, k=10):
if n == 2 or n == 3:
return True
if n <= 1 or n % 2 == 0:
return False
# 将 n - 1 分解为 d * 2^r
d = n - 1
r = 0
while d % 2 == 0:
d //= 2
r += 1
# 进行 k 次测试
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_large_prime(n_bits):
while True:
p = random.getrandbits(n_bits)
if is_prime(p):
return p
```
上面的代码中,`is_prime(n, k=10)` 函数使用 Miller-Rabin 算法判断一个数是否为素数,其中参数 `k` 表示进行测试的次数(默认为 10 次)。`generate_large_prime(n_bits)` 函数使用随机数生成器生成一个 `n_bits` 位的大素数。
阅读全文