密码学算法 - Miller-Rabin 素数检验 | Alice and Bobの神秘小屋

当你需要验证一个大数是否为素数时，Miller-Rabin 算法就像一位经验丰富的侦探🕵️‍♂️，能在短时间内给出一个可靠的答案，帮助你在数字的迷宫中找到真相。

欢迎来到《密码学核心算法实战》的 Miller-Rabin 素数检验算法专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。

Miller-Rabin算法的原理 🌟

Miller-Rabin算法基于两个数学定理：

费马小定理：如果 $p$ 是素数，且 $a$ 是一个整数，满足 $1 < a < p-1$，那么 $a^{p-1} \equiv 1 \mod p$。
二次剩余相关：如果 $p$ 是奇素数，方程 $x^2 \equiv 1 \mod p$，只有两个解 $x \equiv \pm 1 \mod p$。

首先，将待检验的奇数 $n$ 写成 $n-1 = 2^s \cdot d$ 的形式，其中 $d$ 是奇数。然后使用费马小定理：

$a^{n-1} \equiv a^{2^s \cdot d} \equiv (\ldots ((a^d)^2)^2 \ldots)^2 \equiv 1 \mod n$

如果 $n$ 是素数，最后的结果应该是 $1$。

然后，从后往前看，最后结果为 $1$，那么前一个结果要么是 $1$，要么是 $-1$。所以，如果 $n$ 是素数，那么在 $a^d$ 的平方过程中，只有两个结果：

$a^d \equiv \pm 1 \mod n$，平方后续全是 $1$。
$a^d \not \equiv 1 \mod n$，但在某次平方后变成 $-1$，之后的平方全是 $1$。

注意，如果 $n$ 是合数，那么 $a^d$ 的平方过程中也可能出现 $1$，但前一个结果不是 $1$ 或 $-1$，也就是在某次平方后出现 $1$，但前一个结果不是 $-1$。我们将这个根叫做“非平凡平方根”，如果存在非平凡平方根，那么 $n$ 一定是合数。

综上所述：

如果 $n$ 是素数，那么 $a^d$ 的平方过程中只有两种情况：要么一开始是 $\pm 1$，后面全是 $1$，要么在某次平方后出现 $-1$，之后全是 $1$。

如果出现了非平凡平方根，那么 $n$ 是合数，如果啥也没有出现，那么 $n$ 很可能是合数。

最后，关于 $a$ 的选择，理论上来说，随机选择 $a$ 是可以的，但为了保证算法的确定性，我们可以选择一些特定的 $a$，例如在 $2^{64}$ 内的几个小素数，这样就能保证对于 $2^{64}$ 内的数进行检验时，算法是完全准确的。

Miller-Rabin算法的操作 🙃

输入：一个整数 $n$，以及一个整数 $k$ 表示测试的轮数。
输出：一个布尔值，表示 $n$ 是否为素数。
算法步骤：

如果 $n \leq 1$，返回 False；如果 $n \leq 3$，返回 True；如果 $n$ 是偶数，返回 False。
将 $n-1$ 写成 $2^s \cdot d$ 的形式，其中 $d$ 是奇数。
进行 $k$ 轮测试：
- 选择一个整数 $a$，满足 $1 < a < n-1$。
- 计算 $x = a^d \mod n$。
- 如果 $x \equiv 1 \mod n$ 或 $x \equiv n-1 \mod n$，继续下一轮测试。
- 否则，进行 $s-1$ 次循环：
  - 计算 $x = x^2 \mod n$。
  - 如果 $x \equiv n-1 \mod n$，跳出循环，继续下一轮测试。
- 如果循环结束后 $x \not\equiv n-1 \mod n$，返回 False。
如果所有轮测试都通过，返回 True。

Miller-Rabin算法的实现 😶‍🌫️

这个算法的实现非常简单，核心就是根据上面的原理进行迭代检查。以下是一个Python实现：


def Miller_Rabin(n):
    # 特殊情况
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0:
        return False

    # 把 n-1 写成 d * 2^s
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    # 对 2^64 内确定性测试
    a_list = [2,3,5,7,11,13,17,19,23,29,31,37]
    for a in a_list:
        x = pow(a, d, n) # 计算 a^d mod n
        if x == 1 or x == n-1: 
            # 如果 a^d ≡ 1 (mod n) 或 a^d ≡ -1 (mod n)，继续测试下一个 a
            continue
        for _ in range(s-1):
            x = pow(x, 2, n) # 计算 x^2 mod n
            if x == n-1: # 如果 x^2 ≡ -1 (mod n)，继续测试下一个 a
                break
        else:
            return False
    return True

SageMath 偷懒 🤓👆

有同学说：“博主，博主，你的算法确实很厉害，但是还是太吃操作了，有没有更加简单无脑的用法？”👻
有的，兄弟有的，这样的算法在 SageMath 中早就已经被封装好了🤫，我们直接调用就行了：

from sage.all import is_prime # sage环境中才生效
# 直接调用 is_prime 函数就可以了，它内部已经部署了 Miller-Rabin 算法，并且在此之上还做了很多优化，能够快速准确地判断一个数是否为素数。
flag = is_prime(n) # flag 是一个布尔值，True 表示 n 是素数，False 表示 n 是合数

怎么样，是不是非常简单？🤣👉🤡

上一章：密码学算法 - Wiener算法 👈
下一章：密码学算法 - BSGS一算法 👈
回到开始：关于我 👈