miller-rabin素数检测算法

Miller-Rabin算法是一种常用的素性检测算法，它可以高效地判断一个数是否为素数。该算法的基本思想是利用费马小定理，对于一个奇数$n$，我们可以将$n-1$表示为$2^sd$的形式，其中$d$是一个奇数。然后对于一个给定的$a$，我们可以计算$a^d,a^{2d},...,a^{2^{s-1}d}$，如果存在某个$a^{2^rd}\equiv-1\pmod{n}$，则$n$可能是一个素数。如果对于所有的$r\in[0,s-1]$，都有$a^{2^rd}\not\equiv-1\pmod{n}$，则$n$一定不是素数。在实际应用中，我们可以随机选择$a$，多次进行上述判断，如果每次都得到$n$可能是素数的结论，则$n$很可能是一个素数。

下面是一个Python实现的Miller-Rabin算法：

import random

def is_prime(n, k=10):
    if n == 2 or n == 3:
        return True
    if n <= 1 or n % 2 == 0:
        return False

    # 将n-1表示为2^sd的形式
    s, d = 0, n - 1
    while d % 2 == 0:
        s += 1
        d //= 2

    # 进行k次随机测试
    for i in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for j in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False

    return True

其中，参数$n$是待判断的数，参数$k$是进行随机测试的次数。该函数返回一个布尔值，表示$n$是否为素数。