ミラー–ラビン素数判定法
フェルマーやソロベイ–シュトラッセンの素数判定法と同様、ミラー–ラビン素数判定法も素数に関して成り立つ等式に基づいており、与えられた数についてそれら等式が成り立つかどうかで判定を行う。
まず、有限体 F p ( = Z / p Z ) {\displaystyle \mathbb {F} _{p}\left(=\mathbb {Z} /p\mathbb {Z} \right)} の単位元の平方根についての補題を考える。ここで、p は奇素数である。p を法とした剰余(mod p)において、1と-1の二乗は常に1となる。これらを 1 の「自明な」平方根と呼ぶ。p は素数なので 1 の「自明でない」平方根は存在しない。これを示すため、1 mod p の非自明な平方根を x とする。このとき、以下が成り立つ:
x 2 ≡ 1 ( mod p ) {\displaystyle x^{2}\equiv 1{\pmod {p}}}
x 2 − 1 ≡ 0 ( mod p ) {\displaystyle x^{2}-1\equiv 0{\pmod {p}}}
( x − 1 ) ( x + 1 ) ≡ 0 ( mod p ) {\displaystyle \left(x-1\right)\left(x+1\right)\equiv 0{\pmod {p}}}