- ベストアンサー
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暗号も、いとも簡単に解けてしまう、ということです。
- みんなの回答 (2)
- 専門家の回答
関連するQ&A
- RSA暗号が破れる素因数分解についてです。
自然数 N を、√N (= Nの平方根)未満の自然数であって、末位の数字が1,3,7,9のもののうち、小さいもの順のものどもで以て、割ってゆき、N を素因数分解する計算の、時間計算量のオーダーは、 どれ位のものでしょうか。
- ベストアンサー
- その他([技術者向] コンピューター)
- すばやく素因数分解する方法は?
「暗号解読」(サイモン・シン(著)青木薫(訳) 新潮社)という本を読んで、急に素数のことに関心を持ちました。 数十桁もある数(合成数)を素因数分解するのは、えらく時間がかかることが書かれていました。 中学生が計算する素因数分解や、「エラトステネスのふるい」のほかに、手計算や計算機を使って、合成数から素数を見つける方法(素因数分解)を知りたいので、ご存知の方教えてください。 できれば、計算機科学における現在、最速の素因数分解の方法(アルゴリズム)を知りたいです。
- ベストアンサー
- 数学・算数
- 素因数分解の問題で…
素因数分解の問題で… 中学3年の姪っ子に数学を教えています。 市販の問題集で、解説と回答を見てもどうしても分からない問題があるんです。 〈素因数分解の問題〉 Aは100より小さい自然数で、Aに54をかけると自然数の2乗になるという。このような自然数Aは全部で何個あるか。 〈解答・解説〉 54=2×3の3乗=6×3の2乗だから、A=6×Nの2乗の形になればよい。 A〈100だから、 N=1のとき、A=6 N=2のとき、A=24 N=3のとき、A=54 N=4のとき、A=96 したがって、Aは4個 と参考書には記載されています。 解説の「A=6×Nの2乗の形になればよい。」という理屈が分かりません。 姪っ子に教えられなくて困っています…。 どなたか分かりやすく解説して頂けないでしょうか? よろしくお願い致します!
- ベストアンサー
- 数学・算数
- 素因数分解でわからない問題があります。教えていただ
けますでしょうか。 勉強していて、下記の問題がどうしてもわかりません。 解答はついているのですが、考え方がわかりません。 教えていただけないでしょうか? 問い 56にできるだけ小さい自然数をかけて、ある整数の二乗にしたい。どんな数をかければよいか? 素因数分解はできるのですが(2の3乗X7)、その後の考え方がわかりません。 ちなみに答えは2X7=14 です。 解説に、56=2の3乗x7=2の2乗x(2x7) よって、2x7=14とありますが、 この解説がまったく理解できません。 2x7=14が何を意味するのかがわかりません。 どう考えればよいのでしょうか? 同じく 360を自然数でわって、ある整数の2乗にしたい。どんな数でわればよいか? という問いも、素因数分解から先の考え方がわからず、解けません。 (答え10,40,90,360)。 どなたか 解き方(考え方)を教えていただけますでしょうか。
- ベストアンサー
- 数学・算数
- 学校でRSA暗号について勉強して分からないところがありましたので質問し
学校でRSA暗号について勉強して分からないところがありましたので質問します。 暗号文の作成者をAさん、復号者をBさんとします。 Aさんは暗号文と公開鍵{e,n}を一般に公開しますよね? 暗号文を復号化するには秘密鍵が必要ですが、Bさんはeとnしか分からない(一般の人と得られる情報が同じ)のにどうやって秘密鍵を作成するのですか?nのもとになっている2つの素数がわからないことには秘密鍵が作成できないとおもうのですが… RSA暗号はnの素因数分解が計算量的に困難だから安全なんですよね?Bさんはどうやって2つの素数を特定するのでしょうか? 教えてください。
- ベストアンサー
- ネットワーク
- RSA 暗号の、最も簡単な破り方は、これですね?
RSA 暗号の、最も簡単な破り方は、これですね?: 暗号文中の自然数をNとする。 1.ルートN 未満の全ての奇数nについて、nが素数か否か、AKS素数判定法で判定する。 https://ja.wikipedia.org/wiki/AKS%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95 2.nが素数ならば、Nをnで割る。
- ベストアンサー
- その他([技術者向] コンピューター)
お礼
謬見でしかない愚論を御批判いただきまして、誠に誠に有難う御座いました。深謝に堪えません。
補足
上記の方法では駄目な事は分かりました。が、それでも、結局、もはや、RSA暗号はアウトです。∵、ツイッターの @koitiluv1842 の拙「固定されたツイート」(Pinned Tweet) スレ、及び、このOKWave 、並びに、ヤフー知恵袋に掲げて居ります、小林吹代氏の、「RSA 暗号が破れ」ると仰る素数生成公式や、菅野正人(かんのまさと)氏(菅野氏も「RSA暗号の終焉」という旨の事を言って居られます。)および故・川村甲子郎氏の素数生成アルゴリズム等々を用いれば、ごく初等的な計算で、ごく短時間に、任意の n に対して、n 番目の素数が割り出せますので。