素数

素数

Prime Number

1とその数以外に約数を持たない1より大きな自然数

nが素数であるかどうかを判定するには、nを\sqrt{n}までの素数で割った剰余が全て0でないかどうかを調べればよいが、もっと効率的に判定できる方法も多数存在する。素数判定アルゴリズムの代表的なものとしては、AKSアルゴリズム、Rabin-Millerテストなどがあげられる。

素数でない自然数は合成数と呼ばれる。

判定法

Miller-Rabin法

確率的判定法。速いのが特徴。

AKS法

確定的判定法。

nが素数かどうか判定する際に最悪時で\tilde{O}((\log n)^{7.5})掛かる。

Sophie Germain仮定*1やアルチン予想が正しいならば\tilde{O}((\log n)^6)まで下がる

*1:n,2n+1が両方ともが素数というnは無限に存在する

* はてなダイアリーキーワード:素数