ミラー-ラビン素数判定法

ミラー-ラビン素数判定法とは

ミラー-ラビン素数判定法またはラビン-ミラー素数判定法は、与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種。フェルマーの素数判定法や Solovay-Strassen 素数判定法と同じく、乱択アルゴリズムの一種である。Gary L. Miller が最初に開発した手法は未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムだったが、マイケル・ラビンはこれを無条件の確率的アルゴリズムに修正した。

• 出典: フリー百科事典『ウィキペディア（Wikipedia）』
• [ ミラー-ラビン素数判定法の改定履歴 ]