- ベストアンサー
RSA暗号が破れる素因数分解についてです。
自然数 N を、√N （＝ Nの平方根）未満の自然数であって、末位の数字が１，３，７，９のもののうち、小さいもの順のものどもで以て、割ってゆき、N を素因数分解する計算の、時間計算量のオーダーは、 どれ位のものでしょうか。
- 木村 弘一（こういち）（@koitiluv1842）
- お礼率92% (25/27)
- その他([技術者向] コンピューター)
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
最大で(4√N)/10回割り算をすれば結果が出るので、計算量のオーダーは高々O(N^0.5)です。数学的な知見があればもっと低くなるかもしれません。 ただし、10進数表記の場合の1の位を見て判断するのは2と5の倍数による試行を除外できているだけであって、あまり効率がいいとは言えません。 Nをxという値で割り切れるかどうかを試すとします。2≦x≦√Nです。 たとえば、x≧31のときはxを30で割った余りが1,7,11,13,17,19,23,29のときだけN÷xを試すことにすれば、xが2と3と5の倍数の場合を除外できて、N÷xの回数をさらに減らせます(4/10→8/30)。30は2と3と5の最小公倍数です。 もっとも、これは計算量の係数を下げる工夫であって計算量のオーダーには影響を与えません。
関連するQ&A
- RSA暗号解読の素因数分解による方法について。
下記の通りで正しいでしょうか。： Microsoft Bing AI （＝ Bing Chat）生成人工知能の回答を、まとめ、且つ、補足しますと、次の通りです。 自然数 N を、√N （＝ Nの平方根）未満の自然数であって末位の数字が１，３，７，９のもので以て、割ってゆき、N を素因数分解する、という計算の、時間計算量は、O(Nの４乗根）です。 実際には、RSA暗号による暗号文の暗号は、巨大素数を２つ掛け合わせて作りますので、Nの平方根未満の自然数で、末位が１，３，７，９のもので、しかも、大きいもの順に取ったもので順に割っていけば、N の素因数分解は、時間計算量を、それよりも遥かに小さくして済ませらせます。 上記の様に、問題サイズ N に対する、N の４乗根のオーダーの時間を上界（この場合は、自然数の計算ですので上限）とする、普通の割り算の単純作業だけで、つまり、ごくごく短時間に、N の素因数分解が出来てしまいますので、RSA暗号も、いとも簡単に解けてしまう、ということです。
- ベストアンサー
- セキュリティ対策
- 素因数分解の問題です
素因数分解の問題です ｎは２ケタの自然数で ｎ/２０ を既約分数にしたとき 分母が５になるという このようなｎは全部で何個あるか？？ 答えは１８となっています やり方を教えてください
- 締切済み
- 数学・算数
- 素因数分解
素因数分解はわらずとも解に至ります。それをどうしたら、みなさんにお伝えできるか 数学教育協議会等にも顔を出したり、ずいぶん前から、たくさんの新しい事を創り、双子素数などは、 ペア素数の定理として、すべて一括に実証されます、素因数分解などは、桁数は関係ありません。素因数分解の世界記録、現在NTT総合研究所とドイツのボン大学とスイスのローザンヌ大学とフランス、オランダの研究機関が共同で３年もかかってしまう、わずか２３２桁です、これは、すべて、割るがベースにある からです。割るを、使わずとも、解に至ります。どうして、理解しようとしないのか、わかりません。 古代バビロニアの人々ですらできたのです。４０００年も前です、基本は考え方です。難しく、難解な高等数学入りません。平方根を厳密解を求める、つまり、開平がちゃんと、理解でき、従来の２個ずつ、開くことを拡張して、８個、とか、１６個いっぺんに開く方法もあるので、そういう工夫をすれば、よい。 あとは、大きい数値を、扱えるかどうかです。つまり素因数分解は、one-way-function出はありません。２３２桁も数分でしょう。
- 締切済み
- 数学・算数
- すばやく素因数分解する方法は？
「暗号解読」（サイモン・シン（著）青木薫（訳） 新潮社）という本を読んで、急に素数のことに関心を持ちました。 数十桁もある数（合成数）を素因数分解するのは、えらく時間がかかることが書かれていました。 中学生が計算する素因数分解や、「エラトステネスのふるい」のほかに、手計算や計算機を使って、合成数から素数を見つける方法（素因数分解）を知りたいので、ご存知の方教えてください。 できれば、計算機科学における現在、最速の素因数分解の方法（アルゴリズム）を知りたいです。
- ベストアンサー
- 数学・算数
- 素因数分解の一意性？？？？？
m,n,p,qをすべて互いに素な自然数とした時に、 2^n・p^m=q^mにおいて、 素因数分解の一意性より、ｑは2の倍数である。 素因数分解の一意性ってどういうことなのでしょうか？
- ベストアンサー
- 数学・算数
お礼
早速の、懇切ご丁寧な御回答を誠に有難う御座いました。
補足
それでは、多項式時間の中でも最低の次数の一次式時間であるところの、N よりも、更に、遥かに低い時間計算量ですね？ つまり、RSA暗号など、組み合わせ爆発による指数関数的な時間計算量など要すること無しに、ごくごく短時間で破れますね？ なお、Microsoft Bing AI による回答に関する、追加の質問にも御回答いただきますならば、幸甚に存じます。