巨大な素数の作り方

Question

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

dumdummy · Accepted Answer

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

terra5 · Answer

ブルーバックスの暗号の数理って本にいくらか公開鍵暗号の解説があります。

素数の生成ですが、エラトステネスのふるいは、計算量とか使用メモリ量とか考えると,巨大な素数の生成は無理でしょう。

ところで、nが素数の判定ですが、・n 以下の整数まで調べれば十分です。
もし、・nより大きい因数があるなら、もう一方はかならず・nより小さい数になるからです。


dumdummyさんはほぼ間違いなく・・とかかれていますが、ほぼでなく、確実に素数かどうかの判定を高速にする方法はあります。

フェルマーテストは素数でない数を判定する方法なので、これだけでは不十分なのは確かですが。

また、こういう整数計算は一般的に面倒な部類にはいります。
たかだか、64bit程度の数字を使うなら速いでしょうが。

nozomi500 · Answer

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

poor_Quark · Answer

私は、門外漢（専門分野といえるようなものはありませんが）ですが、多少の興味がありまして、書き込みをさせていただきます。

　下記ＵＲＬにあるような仮想分散サービスが、本格稼働することを期待したいと思います。公開鍵・秘密鍵などのセキュリティに関することですので、生産性は十分に見込まれると思いますので、うまく実用化すればサービスとして提供されると思います。

　いくら、整数計算とはいえこれくらいのオーダーになると、分散処理でないと無理だと思うのですが。素数計算に関しては「エラトステネスのふるい」意外に知識はありません。考えてみればだれでも簡単に、しかも短時間に扱えれば鍵としての安全性は低いことになりますしね。

参考URL：http://www.fri.fujitsu.com/hypertext/fri/ec/00_9/19.html

巨大な素数の作り方

超簡単な方法はないですが、、、

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

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

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

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

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