素性测试python代码
时间: 2023-11-09 19:02:14 浏览: 58
素性测试是判断一个数是否为质数的方法之一,以下是一个简单的 Python 代码实现:
```python
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**0.5)+1):
if n % i == 0:
return False
return True
```
这个函数接受一个整数作为参数,如果这个整数是质数则返回 True,否则返回 False。该函数的实现方法是从 2 到该数的平方根进行遍历,如果该数能被其中任意一个数整除,则该数不是质数。
相关问题
米勒罗宾素性测试算法python
米勒罗宾素性测试算法是一种用于判断一个数是否为素数的算法。在Python中,可以通过编写相应的代码来实现该算法。具体实现过程可以分为以下几个步骤:
1.生成k和q:根据被检验数n,生成k和q,其中k和q满足n-1=q*2^k。
2.选择a:从2到n-1中选择一些数作为a,用于后续的检验。
3.检验函数:根据公式(a^q)%n=1和(a^((2^i)*q))%n=n-1,判断被检验数n是否为素数。
4.Miller_Rabin_Test函数:根据上述步骤,编写Miller_Rabin_Test函数,用于判断一个数是否为素数。
在Python中,可以使用import math导入math库,使用该库中的sqrt函数来计算平方根。具体实现代码如下:
```
import math
# k、q生成
def get_KQ(n: int)-> list:
Q = int(n - 1)
K = 0
while(Q%2==0):
K += 1
Q = int(Q / 2)
return K, Q
# 素数判断
def isPrime(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
# a选择
def get_A(n: int, nums=1)-> list:
A = []
flag = 0
for i in range(2,n):
if(flag<nums):
if(isPrime(i)):
A.append(i)
flag += 1
else:
break
return A
# 检验函数
def judge_(n: int, k: int, q: int, a: int)-> bool:
if (a**q)%n==1:
return True
for i in range(k):
if (a**((2**i)*q))%n==n-1:
return True
return False
# Miller_Rabin_Test
def M_R_Test(n, nums):
k, q = get_KQ(n)
a = get_A(n, nums=nums)
p = 1
for i in a:
if judge_(n, k, q, i)==True:
p *= 0.25
else:
p = 1
break
return p
if __name__=='__main__':
# 用于检验的素数数量
nums = 10
# 被检验数
n = 49921
# 检验结果
print(f'\nn为合数的概率为:{M_R_Test(n, nums)}')
```
Miller-Rabin素性检验 python
Miller-Rabin素性检验是一种用于判断一个大整数是否为素数的方法,它比Fermat素性检验更加可靠。下面是一个用Python实现的Miller-Rabin素性检验的代码示例:
```python
import random
def miller_rabin(n, k=10):
"""
Miller-Rabin素性检验
"""
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
r, s = 0, n-1
while s % 2 == 0:
r += 1
s //= 2
for i in range(k):
a = random.randint(2, n-2)
x = pow(a, s, n)
if x == 1 or x == n-1:
continue
for j in range(r-1):
x = pow(x, 2, n)
if x == n-1:
break
else:
return False
return True
```
其中,`miller_rabin`函数用于进行Miller-Rabin素性检验。参数`n`为待检验的大整数,参数`k`为检验次数,一般取10次即可。函数返回`True`表示`n`可能是素数,返回`False`表示`n`一定不是素数。
Miller-Rabin素性检验的正确性已经被证明。相比Fermat素性检验,它的错误概率更小,同时也可以检测出更多的合数。因此,Miller-Rabin素性检验常常被用于实际的应用中。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)