- ベストアンサー
巨大な素数の作り方
nozomi500の回答
- nozomi500
- ベストアンサー率15% (594/3954)
結局は、オーソドックスに「エラトステネスのふるい」でやるんだ、と聞いた事がありますが・・・。
関連する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桁の素数を生成しているのでしょうか。 もしくは、計算済みの素数リストや固定の値を使用しているのでしょうか。 (後者はあり得ないとは思いますが…) 宜しくお願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
- DSA暗号とRSA暗号
SSHサーバーを立てるときに暗号化方式として、DSA暗号とRSA暗号方式があるようですが、 http://computers.yahoo.co.jp/dict/ でDSA暗号方式が掲載されていないことを見ると RSA暗号方式の方が安全であり、なおかつ最新で主流のものと考えてよろしいでしょうか? また、DSA暗号とRSA暗号方式のメリットやデメリットなどご存知の方、ご教授できればありがたく思います。
- ベストアンサー
- ネットワーク
- 学校でRSA暗号について勉強して分からないところがありましたので質問し
学校でRSA暗号について勉強して分からないところがありましたので質問します。 暗号文の作成者をAさん、復号者をBさんとします。 Aさんは暗号文と公開鍵{e,n}を一般に公開しますよね? 暗号文を復号化するには秘密鍵が必要ですが、Bさんはeとnしか分からない(一般の人と得られる情報が同じ)のにどうやって秘密鍵を作成するのですか?nのもとになっている2つの素数がわからないことには秘密鍵が作成できないとおもうのですが… RSA暗号はnの素因数分解が計算量的に困難だから安全なんですよね?Bさんはどうやって2つの素数を特定するのでしょうか? 教えてください。
- ベストアンサー
- ネットワーク
お礼
ご回答ありがとうございます。 ちょう時間かかっちゃいますね。