巨大な素数の作り方

質問

RSA暗号で巨大な素数（10^100とかのオーダー）を使うのですが、
そんな巨大な素数はどうやって見つけるのですか？

超簡単な方法がありそうですけど。

回答No.2

noname#215903 · ベストアンサー

超簡単な方法はないですが、、、
素数を生成するというよりは、
適当に数字を決めて、それが素数かどうか判定します。
100%素数であることを証明するには、
それより小さい数すべてで割ってみる、なのですが、
これでは時間がいくらあっても足りません。
そこで、合格したらその数は「ほぼ間違い無く」素数であるといわれるようなテストが用意されています。
手元の書籍「暗号・ゼロ知識証明・数論、共立出版、
情報処理学会監修、岡本龍明・太田和夫共編」に
詳しくかかれています。
これによると、Fermatテスト、SoLovay-Strassenテスト、
Miller-Rabbinテストに合格したらそれは素数とみなすと。
他にもAdleman-Rumely法、Jacobi和テスト・Cohen-Lenstra法、楕円曲線法、、、などあるようです。
私もちゃんと理解しているわけではなく、詳細は説明できませんので、
上記の名前で検索or書籍を参照してください。

お礼

ご回答ありがとうございました。

自分でも調べてみたのですが、素数を見つける公式は見つかってないそうですね。
RSA暗号では鍵を作る上で巨大な素数を必要とするのですけど、
その素数を見つけるには、暗号を解読するコストの^(1/2)かかるので、
そりゃたいへんだなあ、と。

素数テーブルみたいなものがあるのでしょうか？

回答No.4

terra5

ブルーバックスの暗号の数理って本にいくらか公開鍵暗号の解説があります。

素数の生成ですが、エラトステネスのふるいは、計算量とか使用メモリ量とか考えると,巨大な素数の生成は無理でしょう。

ところで、nが素数の判定ですが、・n 以下の整数まで調べれば十分です。
もし、・nより大きい因数があるなら、もう一方はかならず・nより小さい数になるからです。

dumdummyさんはほぼ間違いなく・・とかかれていますが、ほぼでなく、確実に素数かどうかの判定を高速にする方法はあります。

フェルマーテストは素数でない数を判定する方法なので、これだけでは不十分なのは確かですが。

また、こういう整数計算は一般的に面倒な部類にはいります。
たかだか、64bit程度の数字を使うなら速いでしょうが。

お礼

フェルマーテストは「素数でない」ことを判定するので、素数を見つけるには
大変になっちゃいますね。nが素数の積の場合は、
素数になってしまう場合もあるそうで。

とここまで書いて、以下のサイトをみつけました。

http://hanran.tripod.com/crypt/faq/appendix2.html

やっぱり「適当な数字が素数かどうか？」で素数を見つけるのですね。

自己解決見たくなってしまいましたが、ありがとうございｍした。

回答No.3

nozomi500

結局は、オーソドックスに「エラトステネスのふるい」でやるんだ、と聞いた事がありますが・・・。

お礼

ご回答ありがとうございます。

ちょう時間かかっちゃいますね。

回答No.1

poor_Quark

私は、門外漢（専門分野といえるようなものはありませんが）ですが、多少の興味がありまして、書き込みをさせていただきます。

　下記ＵＲＬにあるような仮想分散サービスが、本格稼働することを期待したいと思います。公開鍵・秘密鍵などのセキュリティに関することですので、生産性は十分に見込まれると思いますので、うまく実用化すればサービスとして提供されると思います。

　いくら、整数計算とはいえこれくらいのオーダーになると、分散処理でないと無理だと思うのですが。素数計算に関しては「エラトステネスのふるい」意外に知識はありません。考えてみればだれでも簡単に、しかも短時間に扱えれば鍵としての安全性は低いことになりますしね。

参考URL：

http://www.fri.fujitsu.com/hypertext/fri/ec/00_9/19.html

お礼

ご回答ありがとうございました。

力技しかないのかなあ。