Miller-Rabin素性检验 python

Miller-Rabin素性检验是一种用于判断一个大整数是否为素数的方法，它比Fermat素性检验更加可靠。下面是一个用Python实现的Miller-Rabin素性检验的代码示例：

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素性检验常常被用于实际的应用中。