生成大素数的 Python 代码优化:避免无限循环
你是正确的,我没有在修正代码时进行必要的修改。对于生成大素数的代码,确实不需要使用 'while True' 循环。
以下是经过修正的生成大素数的代码示例:
import random
import math
def is_prime(n, k=5):
if n <= 1:
return False
if n <= 3:
return True
# 将 n - 1 分解成 (2^r) * d
r = 0
d = n - 1
while d % 2 == 0:
r += 1
d //= 2
# 进行 k 次 Miller-Rabin 素性测试
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(bits):
# 生成一个随机的奇数
num = random.getrandbits(bits)
num |= (1 << bits - 1) | 1
# 检查是否为素数
while not is_prime(num):
num += 2
return num
# 在这里指定所需的位数
bits = 1024
prime = generate_large_prime(bits)
print(prime)
在修正后的代码中,我们生成一个随机的奇数 'num',并将其最高位和最低位设置为 1。然后,我们使用 'while' 循环,不断增加 'num' 的值,直到找到一个满足条件的素数。
在每次循环中,我们使用 'is_prime' 函数进行 Miller-Rabin 素性测试,并检查 'num' 是否为素数。如果不是素数,我们增加 'num' 的值,通过循环继续测试,直到找到一个满足条件的素数为止。
通过这种修正后的代码,我们可以确保生成满足要求的大素数,并避免无限循环的问题。非常抱歉之前的混淆造成的困惑,感谢你的耐心指正。
原文地址: http://www.cveoy.top/t/topic/bBLb 著作权归作者所有。请勿转载和采集!