ミラー–ラビン素数判定法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/10/26 15:54 UTC 版)
ミラー–ラビン素数判定法（英: Miller–Rabin primality test）またはラビン–ミラー素数判定法（英: Rabin–Miller primality test）は、与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種。フェルマーの素数判定法や ソロベイ–シュトラッセン素数判定法と同じく、乱択アルゴリズムの一種である。Gary L. Miller が最初に開発したMillerテストは未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムだったが、マイケル・ラビンがこれを無条件の確率的アルゴリズムに修正した。
[続きの解説]
「ミラー–ラビン素数判定法」の続きの解説一覧
- 1 ミラー–ラビン素数判定法とは
- 2 ミラー–ラビン素数判定法の概要
- 3 コード例
- 4 判定の正確度
- 5 決定的アルゴリズム
- 6 参考文献
- 7 外部リンク
- ミラー–ラビン素数判定法のページへのリンク
