- ベストアンサー
巨大な素数の作り方
- みんなの回答 (4)
- 専門家の回答
質問者が選んだベストアンサー
- ベストアンサー
超簡単な方法はないですが、、、 素数を生成するというよりは、 適当に数字を決めて、それが素数かどうか判定します。 100%素数であることを証明するには、 それより小さい数すべてで割ってみる、なのですが、 これでは時間がいくらあっても足りません。 そこで、合格したらその数は「ほぼ間違い無く」素数であるといわれるようなテストが用意されています。 手元の書籍「暗号・ゼロ知識証明・数論、共立出版、 情報処理学会監修、岡本龍明・太田和夫共編」に 詳しくかかれています。 これによると、Fermatテスト、SoLovay-Strassenテスト、 Miller-Rabbinテストに合格したらそれは素数とみなすと。 他にもAdleman-Rumely法、Jacobi和テスト・Cohen-Lenstra法、楕円曲線法、、、などあるようです。 私もちゃんと理解しているわけではなく、詳細は説明できませんので、 上記の名前で検索or書籍を参照してください。
その他の回答 (3)
- terra5
- ベストアンサー率34% (574/1662)
ブルーバックスの暗号の数理って本にいくらか公開鍵暗号の解説があります。 素数の生成ですが、エラトステネスのふるいは、計算量とか使用メモリ量とか考えると,巨大な素数の生成は無理でしょう。 ところで、nが素数の判定ですが、・n 以下の整数まで調べれば十分です。 もし、・nより大きい因数があるなら、もう一方はかならず・nより小さい数になるからです。 dumdummyさんはほぼ間違いなく・・とかかれていますが、ほぼでなく、確実に素数かどうかの判定を高速にする方法はあります。 フェルマーテストは素数でない数を判定する方法なので、これだけでは不十分なのは確かですが。 また、こういう整数計算は一般的に面倒な部類にはいります。 たかだか、64bit程度の数字を使うなら速いでしょうが。
お礼
フェルマーテストは「素数でない」ことを判定するので、素数を見つけるには 大変になっちゃいますね。nが素数の積の場合は、 素数になってしまう場合もあるそうで。 とここまで書いて、以下のサイトをみつけました。 http://hanran.tripod.com/crypt/faq/appendix2.html やっぱり「適当な数字が素数かどうか?」で素数を見つけるのですね。 自己解決見たくなってしまいましたが、ありがとうございmした。
- nozomi500
- ベストアンサー率15% (594/3954)
結局は、オーソドックスに「エラトステネスのふるい」でやるんだ、と聞いた事がありますが・・・。
お礼
ご回答ありがとうございます。 ちょう時間かかっちゃいますね。
- poor_Quark
- ベストアンサー率56% (1020/1799)
私は、門外漢(専門分野といえるようなものはありませんが)ですが、多少の興味がありまして、書き込みをさせていただきます。 下記URLにあるような仮想分散サービスが、本格稼働することを期待したいと思います。公開鍵・秘密鍵などのセキュリティに関することですので、生産性は十分に見込まれると思いますので、うまく実用化すればサービスとして提供されると思います。 いくら、整数計算とはいえこれくらいのオーダーになると、分散処理でないと無理だと思うのですが。素数計算に関しては「エラトステネスのふるい」意外に知識はありません。考えてみればだれでも簡単に、しかも短時間に扱えれば鍵としての安全性は低いことになりますしね。
お礼
ご回答ありがとうございました。 力技しかないのかなあ。
関連するQ&A
- RSA暗号に関し、素数p.qが、それぞれ5、11であり、かつ、暗号化鍵
RSA暗号に関し、素数p.qが、それぞれ5、11であり、かつ、暗号化鍵eが23のとき、復号鍵dを求める考え方の手順を教えてください。さらにこれらを使って平文2を暗号化するにはどのようにすればいいでしょうか。
- ベストアンサー
- ネットワーク
- RSA暗号で初めに選択2つの数について
RSA暗号で初めに選ぶ数(p,q)で、2つの内どちらかが合成数であるとき、復号化がうまくいかない場合があります。どうして復号化がうまくいかなくのかわかりません。教えてください。
- ベストアンサー
- 数学・算数
- RSA暗号について教えてください
RSA暗号がどのようなものか、また仕組みについて教えて下さい。調べても分からなかったので、できるだけわかりやすく教えて下さい。また、RSA暗号を用いて、二桁程度の素数を二つ使って暗号の仕方、また戻し方の例を教えてください。お願いします。
- ベストアンサー
- SE・インフラ・Webエンジニア
- RSA暗号解読の素因数分解による方法について。
下記の通りで正しいでしょうか。: Microsoft Bing AI (= Bing Chat)生成人工知能の回答を、まとめ、且つ、補足しますと、次の通りです。 自然数 N を、√N (= Nの平方根)未満の自然数であって末位の数字が1,3,7,9のもので以て、割ってゆき、N を素因数分解する、という計算の、時間計算量は、O(Nの4乗根)です。 実際には、RSA暗号による暗号文の暗号は、巨大素数を2つ掛け合わせて作りますので、Nの平方根未満の自然数で、末位が1,3,7,9のもので、しかも、大きいもの順に取ったもので順に割っていけば、N の素因数分解は、時間計算量を、それよりも遥かに小さくして済ませらせます。 上記の様に、問題サイズ N に対する、N の4乗根のオーダーの時間を上界(この場合は、自然数の計算ですので上限)とする、普通の割り算の単純作業だけで、つまり、ごくごく短時間に、N の素因数分解が出来てしまいますので、RSA暗号も、いとも簡単に解けてしまう、ということです。
- ベストアンサー
- セキュリティ対策
- RSA暗号の一般的な素数生成方法
一般的なRSA暗号について質問です。 RSAでは鍵の生成に、大きな素数 p, q および (p-1)*(q-1)と互いに素となる素数eを使用します。 ただ、p, qの一般的に使用される桁数は1024bit(300桁超)であるため、素数の生成に非常に大きな時間がかかってしまいます。 e は3か65537を使用することで生成のための計算を省くことができますが… RSAで暗号鍵を生成する際に300桁もの素数を毎回計算して生成するのは時間がかかりすぎるため現実的ではないと思いますが、実際にはどのようにして300桁の素数を生成しているのでしょうか。 もしくは、計算済みの素数リストや固定の値を使用しているのでしょうか。 (後者はあり得ないとは思いますが…) 宜しくお願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
- 学校でRSA暗号について勉強して分からないところがありましたので質問し
学校でRSA暗号について勉強して分からないところがありましたので質問します。 暗号文の作成者をAさん、復号者をBさんとします。 Aさんは暗号文と公開鍵{e,n}を一般に公開しますよね? 暗号文を復号化するには秘密鍵が必要ですが、Bさんはeとnしか分からない(一般の人と得られる情報が同じ)のにどうやって秘密鍵を作成するのですか?nのもとになっている2つの素数がわからないことには秘密鍵が作成できないとおもうのですが… RSA暗号はnの素因数分解が計算量的に困難だから安全なんですよね?Bさんはどうやって2つの素数を特定するのでしょうか? 教えてください。
- ベストアンサー
- ネットワーク
- DSA暗号とRSA暗号
SSHサーバーを立てるときに暗号化方式として、DSA暗号とRSA暗号方式があるようですが、 http://computers.yahoo.co.jp/dict/ でDSA暗号方式が掲載されていないことを見ると RSA暗号方式の方が安全であり、なおかつ最新で主流のものと考えてよろしいでしょうか? また、DSA暗号とRSA暗号方式のメリットやデメリットなどご存知の方、ご教授できればありがたく思います。
- ベストアンサー
- ネットワーク
お礼
ご回答ありがとうございました。 自分でも調べてみたのですが、素数を見つける公式は見つかってないそうですね。 RSA暗号では鍵を作る上で巨大な素数を必要とするのですけど、 その素数を見つけるには、暗号を解読するコストの^(1/2)かかるので、 そりゃたいへんだなあ、と。 素数テーブルみたいなものがあるのでしょうか?