Miller-Rabin 素数判定法 は、正整数 $n$ が与えられたときに、「 $n$ が素数であるか否か」を判定する確率的アルゴリズムである。 1 回の試行にかかる計算量は $O(\log^3 n)$ であり