使用python给出完整运行代码,尝试使用米勒拉宾素数判定算法生成1024位大素数
时间: 2024-11-22 17:47:23 浏览: 12
米勒-拉宾素数检验是一种概率性的素数测试,用于判断一个较大的合数是否可能是素数。以下是使用Python实现的一个简单版本的米勒-拉宾素数判定算法示例:
```python
import random
def is_prime(n, k=5): # 米勒-拉宾素数检验,默认k次试验
if n <= 1 or (n % 2 == 0 and n > 2): # 非质数的基本检查
return False
s = n - 1
r = 0
while s % 2 == 0:
s //= 2
r += 1
for _ in range(k):
a = random.randint(2, n - 2) # 选择随机数a作为试商
x = pow(a, s, 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
# 生成1024位的大素数
def generate_large_prime(bit_length=1024):
while True:
p = random.getrandbits(bit_length)
if is_prime(p):
return p
large_prime = generate_large_prime()
print("生成的1024位大素数:", large_prime)
阅读全文