OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

巨大な素数の作り方

  • 暇なときにでも
  • 質問No.176562
  • 閲覧数969
  • ありがとう数5
  • 気になる数0
  • 回答数4
  • コメント数0

お礼率 41% (35/85)

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

超簡単な方法がありそうですけど。
通報する
  • 回答数4
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.2

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

お礼率 41% (35/85)

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

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

素数テーブルみたいなものがあるのでしょうか?
投稿日時 - 2001-11-29 12:35:52
-PR-
-PR-

その他の回答 (全3件)

  • 回答No.1
レベル14

ベストアンサー率 56% (1020/1799)

 私は、門外漢(専門分野といえるようなものはありませんが)ですが、多少の興味がありまして、書き込みをさせていただきます。  下記URLにあるような仮想分散サービスが、本格稼働することを期待したいと思います。公開鍵・秘密鍵などのセキュリティに関することですので、生産性は十分に見込まれると思いますので、うまく実用化すればサービスとして提供されると思います。  いくら、整数計算とはいえこれくらいのオ ...続きを読む
 私は、門外漢(専門分野といえるようなものはありませんが)ですが、多少の興味がありまして、書き込みをさせていただきます。

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

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

お礼率 41% (35/85)

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

力技しかないのかなあ。
投稿日時 - 2001-11-29 12:08:02

  • 回答No.3
レベル14

ベストアンサー率 15% (594/3954)

結局は、オーソドックスに「エラトステネスのふるい」でやるんだ、と聞いた事がありますが・・・。 ...続きを読む
結局は、オーソドックスに「エラトステネスのふるい」でやるんだ、と聞いた事がありますが・・・。
お礼コメント
leiqunni

お礼率 41% (35/85)

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

ちょう時間かかっちゃいますね。
投稿日時 - 2001-11-30 11:19:24
  • 回答No.4
レベル13

ベストアンサー率 34% (574/1662)

ブルーバックスの暗号の数理って本にいくらか公開鍵暗号の解説があります。 素数の生成ですが、エラトステネスのふるいは、計算量とか使用メモリ量とか考えると,巨大な素数の生成は無理でしょう。 ところで、nが素数の判定ですが、・n 以下の整数まで調べれば十分です。 もし、・nより大きい因数があるなら、もう一方はかならず・nより小さい数になるからです。 dumdummyさんはほぼ間違いなく・ ...続きを読む
ブルーバックスの暗号の数理って本にいくらか公開鍵暗号の解説があります。

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

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


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

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

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

お礼率 41% (35/85)

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

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

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

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

自己解決見たくなってしまいましたが、ありがとうございmした。
投稿日時 - 2001-11-30 11:40:50
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ