Miller-Rabin Primality Test
ミラー・ラビン法は確率的な素数判定法である。n-1=2^s*d と書き、a^d≡1 またはある a^(2^r*d)≡-1 (mod n) を検査する。1 ラウンドの誤判定確率は高々 1/4 である。
目的
素数判定を効率よく確率的に行う。RSA の大きな素数生成に使われる。
メカニズム
n-1=2^s*d に対して、ランダムな a∈[2,n-2] を選び x=a^d mod n を計算する。x=1 または n-1 なら n はおそらく素数である。そうでなければ s-1 回まで二乗し、n-1 になればおそらく素数、ならなければ n は合成数と確定する。k ラウンド後の誤り確率は高々 4^(-k) である。
ユースケース
- RSA素数の生成
- 素数判定アルゴリズム（primality test）
- 暗号ライブラリでの実装（cryptography）