ミラー素数判定法
未証明の拡張リーマン予想に依存しているため、動作が数学的に保証されないアルゴリズム 未証明の予想に依存していないから
判定する範囲
判定対象の数$ nが合成数なら、$ nと互いに素な「強い嘘つき」の $ aは群$ (\Z/n\Z)^*の真の部分群に含まれる。 つまり$ (\Z/n\Z)^*の生成元集合の全$ aについて判定するとき、その中には必ず$ nの合成性の証拠となる数が含まれる。
拡張リーマン予想が真であると仮定すると、ミラーが既に指摘したように$ \Omicron(\log^2 n)より小さい元から、この集合が生成されることがわかっている。 big O 記法の定数は Eric Bach によって 2 まで減らされた（1990年）。
なので$ \lfloor2\log^2n\rfloorまで調べれば十分だと。Summer498.icon
準備
$ p^nを$ \hat pで表すことにする。
特に$ \hat2は$ \hat2=4や$ \hat2=1024など複数の値を取りうる変数である事に注意。
アルゴリズム
入力: $ n\in\N\quad(n\ge3)
出力: $ nが合成数ならcomposite, さもなくば prime
動作
1. $ n-1=\hat{\bm2}xを満たす$ xを見つける
2. 以下を$ \forall a\in[2,\min(n-1,\lfloor2\log_2^2n\rfloor)] について繰り返す
$ a^x\overset n\equiv1であれば$ aを更新して処理をやり直す（continue）
$ ^{\forall\hat2\le\hat{\bm2}/2}[a^{\hat 2x}\overset n{\not\equiv}-1] なら composite を返す
3. prime を返す
入力: $ n\in\N\quad(n\ge3),$ k\in\N: 判定の正確度を表すパラメータ
出力: $ nが合成数ならcomposite, さもなくば probably prime
動作
1. $ n-1=\hat{\bm2}xを満たす$ xを見つける
2. 以下を$ k回繰り返す
1. $ a\in[1, n-1]\subset\N を乱択する
2. $ a^x\overset n\equiv 1なら$ kを更新して処理をやり直す（continue）
3. $ ^{\forall\hat2\le\hat{\bm2}/2}[a^{\hat2x}\overset n{\not\equiv}-1] なら composite を返す
3. probably prime を返す
評価
探索範囲を入力長の多項式時間で抑えて全探索している 計算量は $ \tilde\Omicron(\log^4n)
多項式時間と言っても$ D^4か～
$ n が十分小さければもっと小さい証拠の可能性のある数の集合で十分らしい
例えば、Jaeschke (1993) は以下を検証した。
もし n < 4,759,123,141 なら、a = 2, 7, 61 について調べればよい。
もし n < 341,550,071,728,321 なら、a = 2, 3, 5, 7, 11, 13, 17 について調べれば十分である。
全ての合成数に対してはこのような集合では不十分らしい
Alford、Granville、Pomerance は、合成数 n について合成性の証拠となる最小の数が$ (\log n)^{\frac1{3\log\log\log n}}より大きい合成数が無数に存在する、
$ Xが十分大きいときには$ X以下のそのような合成数の個数は少なくとも$ X^{\frac1{35\log\log\log X}}であることを示した
また彼らはヒューリスティック的に、$ w 以下の合成性の証拠となる数のある $ n 以下の合成数について $ w のオーダーを$ \Theta(\log n\log\log n)であると示唆した。