仕事で大きな素数を扱う必要がありました (要は RSA 暗号化です)。 仕事で作ったのので当然ソースはお見せできませんが、多倍長クラスを作って、 演算ができるようにし、エラトステネスのふるいや Miller-Rabin 判定を行いました (なお、RSA を取り組む方は「拡張ユークリッド互除法」や「中国剰余定理」 というキーワードも必要でしょう)。
さて、巨大素数を扱うプログラムを作る際に問題なのが、 見たままではそれが素数かどうか分からず、プログラムが正しいのかどうか 分からないことです。 幾つか既知の素数が分かってて、 それをプログラムに食わせてみて素数と出れば安心するのですが、 そういうデータが見つかりませんでした (どっかに CGI か何かで大きい素数を 表示するページがあった気もしますが 10 進法で記述されていたため使えませんでした)。 とゆーわけで後世の方のため、私が得た巨大素数のデータを ここに置いておくことにしました。
なお、素数は鬼のような数があるので以下のような処理で飛ばし飛ばし探しています。
P = 3
for (;;){
if (P.IsPrime()){
P.Print();
P *= 2;
P++;
}else{
P+=2;
}
}
|
素数判定はまず 2 から 1999 まで素数でエラトステネスのふるいをかけ、 残ったものに対し 2,3,5 の Miller-Rabin でチェックを行い、 それも通れば素数としています (データの中に 3 が無いのは Miller-Rabin の 3 で引っかかったため)。 ですから厳密には擬似素数と呼ばれる物が入っている可能性もあります。
最後に、本データは私が作ったプログラムによる結果です。 当然プログラムにミスがあって実は正しくないデータだということだってありえます。 この数値を信用したおかげでデバッグに長いこと苦しむ事態に陥っても、 私は一切責任を負いません。 そういう可能性も頭の隅に置いてお使いください。