- ベストアンサー
巨大な素数の作り方
noname#215903の回答
- ベストアンサー
超簡単な方法はないですが、、、 素数を生成するというよりは、 適当に数字を決めて、それが素数かどうか判定します。 100%素数であることを証明するには、 それより小さい数すべてで割ってみる、なのですが、 これでは時間がいくらあっても足りません。 そこで、合格したらその数は「ほぼ間違い無く」素数であるといわれるようなテストが用意されています。 手元の書籍「暗号・ゼロ知識証明・数論、共立出版、 情報処理学会監修、岡本龍明・太田和夫共編」に 詳しくかかれています。 これによると、Fermatテスト、SoLovay-Strassenテスト、 Miller-Rabbinテストに合格したらそれは素数とみなすと。 他にもAdleman-Rumely法、Jacobi和テスト・Cohen-Lenstra法、楕円曲線法、、、などあるようです。 私もちゃんと理解しているわけではなく、詳細は説明できませんので、 上記の名前で検索or書籍を参照してください。
関連するQ&A
- RSA暗号に関し、素数p.qが、それぞれ5、11であり、かつ、暗号化鍵
RSA暗号に関し、素数p.qが、それぞれ5、11であり、かつ、暗号化鍵eが23のとき、復 号鍵dを求める考え方の手順を教えてください。さらにこれらを使って平文2を暗号化するにはどのようにすればいいでしょうか。
- ベストアンサー
- ネットワーク
- RSA暗号で初めに選択２つの数について
RSA暗号で初めに選ぶ数（p,q）で、２つの内どちらかが合成数であるとき、復号化がうまくいかない場合があります。どうして復号化がうまくいかなくのかわかりません。教えてください。
- ベストアンサー
- 数学・算数
- RSA暗号について教えてください
RSA暗号がどのようなものか、また仕組みについて教えて下さい。調べても分からなかったので、できるだけわかりやすく教えて下さい。また、RSA暗号を用いて、二桁程度の素数を二つ使って暗号の仕方、また戻し方の例を教えてください。お願いします。
- ベストアンサー
- SE・インフラ・Webエンジニア
- RSA暗号解読の素因数分解による方法について。
下記の通りで正しいでしょうか。： Microsoft Bing AI （＝ Bing Chat）生成人工知能の回答を、まとめ、且つ、補足しますと、次の通りです。 自然数 N を、√N （＝ Nの平方根）未満の自然数であって末位の数字が１，３，７，９のもので以て、割ってゆき、N を素因数分解する、という計算の、時間計算量は、O(Nの４乗根）です。 実際には、RSA暗号による暗号文の暗号は、巨大素数を２つ掛け合わせて作りますので、Nの平方根未満の自然数で、末位が１，３，７，９のもので、しかも、大きいもの順に取ったもので順に割っていけば、N の素因数分解は、時間計算量を、それよりも遥かに小さくして済ませらせます。 上記の様に、問題サイズ N に対する、N の４乗根のオーダーの時間を上界（この場合は、自然数の計算ですので上限）とする、普通の割り算の単純作業だけで、つまり、ごくごく短時間に、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さんはどうやって２つの素数を特定するのでしょうか？ 教えてください。
- ベストアンサー
- ネットワーク
- ＤＳＡ暗号とＲＳＡ暗号
ＳＳＨサーバーを立てるときに暗号化方式として、ＤＳＡ暗号とＲＳＡ暗号方式があるようですが、 http://computers.yahoo.co.jp/dict/ でＤＳＡ暗号方式が掲載されていないことを見ると ＲＳＡ暗号方式の方が安全であり、なおかつ最新で主流のものと考えてよろしいでしょうか？ また、ＤＳＡ暗号とＲＳＡ暗号方式のメリットやデメリットなどご存知の方、ご教授できればありがたく思います。
- ベストアンサー
- ネットワーク
お礼
ご回答ありがとうございました。 自分でも調べてみたのですが、素数を見つける公式は見つかってないそうですね。 RSA暗号では鍵を作る上で巨大な素数を必要とするのですけど、 その素数を見つけるには、暗号を解読するコストの^(1/2)かかるので、 そりゃたいへんだなあ、と。 素数テーブルみたいなものがあるのでしょうか？