使用素性检测(如Miller-Rabin)算法生成大素数,写一个可运行的python代码
时间: 2023-12-29 17:02:23 浏览: 33
好的,以下是一个可运行的使用 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
if __name__ == '__main__':
n = int(input("请输入需要生成的素数的位数:"))
prime = generate_prime(n)
print(f"{n} 位素数为:{prime}")
```
你可以直接运行这个代码,并输入需要生成的素数的位数,它会输出一个指定位数的素数。
相关推荐
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)