ミラー–ラビン素数判定法
このアルゴリズムは次のように表現される:
入力: n > 1 {\displaystyle n>1} : 素数判定対象の奇数の整数; k {\displaystyle k} : 判定の正確度を指定するパラメータ
出力: n {\displaystyle n} が合成数なら composite、さもなくば probably prime
n − 1 {\displaystyle n-1} を 2 のべき乗で割って、 2 s ⋅ d {\displaystyle 2^{s}\cdot d} の形式にする。
以下を k {\displaystyle k} 回繰り返す: [ 1 , n − 1 {\displaystyle 1,n-1\ } ] の範囲から a {\displaystyle a} をランダムに選ぶ。