米勒拉宾算法python代码
时间: 2023-10-02 12:12:30 浏览: 60
以下是米勒拉宾算法的 Python 代码实现:
```python
import random
def power(x, y, p):
res = 1
x = x % p
while y > 0:
if y & 1:
res = (res * x) % p
y = y >> 1
x = (x * x) % p
return res
def miller_rabin(n, k):
if n == 2 or n == 3:
return True
if n <= 1 or n % 2 == 0:
return False
# 寻找r和d,使得n-1=d*(2^r)
d = n - 1
r = 0
while d % 2 == 0:
r += 1
d //= 2
# 进行k次测试
for i in range(k):
a = random.randint(2, n-2)
x = power(a, d, n)
if x == 1 or x == n-1:
continue
for j in range(r-1):
x = power(x, 2, n)
if x == n-1:
break
else:
return False
return True
```
其中,`power(x, y, p)` 函数用于计算幂余,`miller_rabin(n, k)` 函数用于判断一个数 `n` 是否为素数,其中 `k` 是测试次数,可以根据需要调整。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)