2010-03-15 素数マスターへの道(5)
■[数学]素数マスターへの道(5) 
試し割の効果
最初に書いたプログラムは、あまり速くはありませんでした。理由は、大きな素数が現れた場合に4千回以上も試し割りをしなければならないからです。プログラムを実行した結果、判定する33,333,333個の整数の中に、素数は3,260,532個でありました。全体の約9.8%と、それほど多くはありません。
素数でない数の中で、3の倍数は11,111,106個もあり、これは全体の約33.3%に相当します。結構たくさんありますね。
フェルマーテストやミラー・ラビンテストを行う場合でも、数十回の割り算が必要になります。それなら、小さな素数での試し割は、篩い落とせる量を考えれば、十分役立ちそうです。
どれぐらい篩い落とせるか
今回扱う問題は、奇数しか出てこないので、3,5,7,...と、3から順に試し割をして篩い落とせる値の数を数えてみました。
ある程度大きな素数になると、篩い落とせる値がグッと減りますが、最初の方はかなりの数を落とせることがわかります。
プログラムを改良
ミラー・ラビンテストを行う前に、幾つかの小さい素数で試し割をしておきます。
for(i=0;i<M;++i) { if( n%3==0 || n%5==0 || n%7==0 || n%11==0 || n%13==0 || n%17==0 || n%19==0 )printf("0"); else if( mrtest(2,n) && mrtest(7,n) )printf("1"); else printf("0"); n=(n+D)%R; }
このように、3から19までの7個の素数で試し割を行うと、試し割りをしない場合87秒に対して、32秒にまで高速化しました。これはすごいですね！
「小さな素数での試し割り」＋「フェルマーテストまたはミラー・ラビンテスト」で、10分近くかかっていた計算が、30秒ちょっとでできてしまいました。
続く
トラックバック - http://d.hatena.ne.jp/Ozy/20100315
水さすようで申し訳ないんですが、フェルマーテストはカーマイケル数に対して高確率でfalse positiveになります。
ミラー・ラビン素数判定は一つの底で判定する度に1/4の確率でしか素数性を担保出来ません。
確実な素数判定となるとAKS素数判定法を使うかエラトステネスの篩で求めるか、検査する数をnとするとn^(1/2)までの数で検算するなどしないと駄目だったはずです。
試し割りと併用する事で擬素数の登場数を減らし、
それでも擬素数が残ればテーブルで持って個別に潰しちゃっても別に構わないのです。
それが邪道と言うなら、ミラーラビンでも、拡張リーマン予想が正しいと仮定すれば
確実な素数判定のできる方法も存在します。
拡張リーマン予想は未解決問題ですけど、
実際に使ってみてもちゃんと素数判定できてるので、大丈夫そうな感じです。
（むしろできなかったら拡張リーマン予想の反証という歴史に残る大発見になるレベル）
問題の値域に限定するならば、2, 7, 61 のたった３つの底で判定するだけでも擬素数は現れなくなります。
本稿の主旨は…と書こうと思ったらすでにロベールさんが書いてくださってたので、省略します^^;まあ、簡単に申しますと、第1回
http://d.hatena.ne.jp/Ozy/20100225#p1
にある、SPOJというサイトのPrime Checkerという問題で最速コードを目指すことを目的としておりまして、本題から逸れて文章量が増えすぎないように、ウィキペディア等で調べられるような一般的なお話はあまり書かないようにしております。
ランキング(http://www.spoj.pl/ranks/PRIC/)のトップは、3秒足らずという超高速なプログラムで33,333,333個の数をすべて判定しています。実際コードを書いてみればわかりますが、これは驚異的な速度です。このコメントを書いている時点で、3秒を切るためのアルゴリズムはわからないのですが、本稿をきっかけとしてさらに凄いアイデアが出ることを期待して書いています。
とはいえ、こうしてご指摘もあったことですし、この辺のもう少し突っ込んだお話も書かせていただきますm(__)m