米勒罗宾素性测试算法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)}')