介绍

\(Miller-\ Rabin\) 是一种基于随机的算法，其主要根据两个定理构建而成。

1、费马小定理

若 \(p\) 是质数，且 \(\gcd(a,p)=1\)，则有 \(a^{p−1}≡1 \pmod p\)。

假设现在要判断 \(x\) 是否为质数，那么就可得出，只需任意找一个数 \(a\)，若其不满足 \(a^{x-1} \equiv 1 \pmod x\)，这个数就不是质数。

二次探测定理

若 \(p\) 是奇质数，那么 \(x^2 \equiv 1\pmod p\) 的解为 \(x \equiv 1 \pmod p\) 或 \(x \equiv p-1 \pmod p\)。

证：

\[\begin{align} x^2 \equiv 1 \pmod p \\ x^2 -1 \equiv 0 \pmod p \\ (x-1) (x+1) \equiv 0 \pmod p \end{align} \]

又 \(\because p\) 为奇质数
\(\therefore p\) 的因数只有 \(1\) 和 \(p\)
$\therefore 只有两解 \(x \equiv 1 \pmod p\) 或 \(x \equiv p-1 \pmod p\)