ミラー–ラビン素数判定法
ウィキペディア フリーな encyclopedia
ミラー–ラビン素数判定法(英: Miller–Rabin primality test)またはラビン–ミラー素数判定法(英: Rabin–Miller primality test)は、与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種。フェルマーの素数判定法や ソロベイ–シュトラッセン素数判定法と同じく、乱択アルゴリズムの一種である。Gary L. Miller が最初に開発したMillerテストは未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムだったが、マイケル・ラビンがこれを無条件の確率的アルゴリズムに修正した。