Introduction

ブログ内検索

  • このサイトの記事を検索 by Google

おすすめの一冊!

無料ブログはココログ

« 「いつふぉろ」リニューアル | トップページ | 素数判定(その2) »

2010-04-13

素数判定

ちょっと気になったので、素数判定について調べてみました。



「素数判定」というのは、ある自然数が素数か否かを判断することです。

    ⇒ 素数判定  --  Wikipedia

原理的には、エラトステネスのふるいとかすれば 100% 確かな答えが得られます。
でも、公開鍵暗号とかで使うような大きな数についてそれをやるのは非現実的。

最近(2002年)になって、多項式オーダの計算時間で素数判定ができるという
すばらしい理論が発表されましたが、多項式の次数が高くて現実には時間がかかる。

    ⇒ AKS素数判定法  --  Wikipedia

というわけで、現実的な解としては、「素数でない数を十分高い確率で弾ける」
アルゴリズムを使ってテストして、そのテストに繰り返しパスした数を
「確率的素数 (probable prime)」として暗号とかに使うことになります。

そのアルゴリズムとしては「ミラー-ラビン素数判定法 (Miller-Rabin
primality test)」というものが有名らしいです。

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

Wikipedia の記事には Ruby のコード例まで載っています(すばらしい!
数式は理解できなくてもコードなら理解できる(ぉ

また、注目すべき記述もあって、

もし n < 4,759,123,141 なら、a = 2, 7, 61 について調べればよい。 もし n < 341,550,071,728,321 なら、a = 2, 3, 5, 7, 11, 13, 17 について調べれば十分である。
とのことです。つまり、48bit 以下の整数なら a = 2, 3, 5, 7, 11, 13, 17 の ケースだけ調べれば 100% 確かな判定ができるということですね。すばらしい。 べき乗の高速化についても Wikipedia の記事が参考になります。 ⇒ 冪乗 -- Wikipedia 「上位桁から計算する方式」とか、面白いですねー じつは、この種の計算(多倍長整数の繰り返し乗算)は GPGPU に向いている のではないかと思っているので、もうちょっと調べてみようと思います。

« 「いつふぉろ」リニューアル | トップページ | 素数判定(その2) »