python 生成大素数

对计算机领域的人来讲，素数总是一个很热门的话题。生成素数在密码学和计算机网络中扮演重要的角色。Python提供了一种简单的方法来生成大素数。

import random
import math
# 基于费马小定理的Miller-Rabin素性测试
def miller_rabin(n, k=5):
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
# 将n⑴转化成(2**r)*d
r = 0
d = n - 1
while d % 2 == 0:
d //= 2
r += 1
# 进行k次测试
for i in range(k):
a = random.randint(2, n⑵)
x = pow(a, d, n)
if x == 1 or x == n⑴:
continue
for j in range(r⑴):
x = pow(x, 2, n)
if x == n⑴:
break
else:
return False
return True
# 生成大素数
def generate_large_prime(bits):
while True:
p = random.getrandbits(bits)
if p % 2 == 0:
p += 1
if miller_rabin(p):
return p
# 测试
bits = 1024
p = generate_large_prime(bits)
print(p)

这段代码使用了Miller-Rabin素性测试的算法，该算法基于费马小定理。它可以很快地判断一个数会不会为素数。

我们先定义了一个函数miller_rabin(n, k)，它用于在k次测试中判断n会不会为素数。如果n是2或3，则直接返回True。如果n是偶数，则直接返回False。接着将n⑴转化成(2**r)*d的情势，d为奇数，r为正整数。然后选取一个2到n⑵之间的随机数a，计算x = a**d mod n。如果x等于1或n⑴，则跳出这次测试。否则，我们用for循环重复r⑴次进行下面的操作：把x的平方对n取模，如果x等于n⑴，则跳出这个循环。如果for循环完以后没有跳出，则表明n是合数，直接返回False。如果完成了k次测试都没有返回False，则表明n多是素数。

然后我们定义了一个函数generate_large_prime(bits)，它用于生成一个二进制位数为bits的素数。它的方法是随机地生成一个大整数，并判断它会不会是素数。如果是素数则返回，否则重新生成。

最后，我们测试了一下这个函数，生成了一个1024位的素数。