- ベストアンサー
素因数分解はなぜ困難？
今暗号について勉強しています。その中に素因数分解が困難であることを利用してつくられた暗号がいくつかありますが、なぜ素因数分解が困難であるのかがわかりません。それを証明する方法などがありましたらなんでもいいので教えてください。
- versusthunder
- お礼率66% (2/3)
- 数学・算数
- 回答数2
- ありがとう数1
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
素因数分解は結局可能性のある素数でつぎつぎと割ってみて、割り切れるかどうかで調べるしか手段なないこと。 この方法だと,桁数が増えたときに計算量が爆発的に増えることによります。 ただし、証明はまだされていないと思います。 ですから数学的には未解決の問題です。 証明は出来ませんが、ある桁数の数をある方法で素因数分解するための平均的な計算量などは計算できますから、 現在の最速の計算機で何億年もかかるとなると、 事実上解読不能ということになります。 もちろん、桁数が多くても2の倍数なんてつかったら、 あっという間に解かれますね(^^; 将来簡単な計算法が見付かる可能性も0ではありませんが、 過去の例からするとこういう問題はできないことが証明されるのがほとんどのようです。
その他の回答 (1)
- ADEMU
- ベストアンサー率31% (726/2280)
以下のサイトが参考になるでしょうか。 http://www.maitou.gr.jp/rsa/rsa14.html
補足
ありがとうございます。なんとなく困難であるということはわかりましたが、はっきり困難であるとういう数学的証明はできないのでしょうか？
関連するQ&A
- すばやく素因数分解する方法は？
「暗号解読」（サイモン・シン（著）青木薫（訳） 新潮社）という本を読んで、急に素数のことに関心を持ちました。 数十桁もある数（合成数）を素因数分解するのは、えらく時間がかかることが書かれていました。 中学生が計算する素因数分解や、「エラトステネスのふるい」のほかに、手計算や計算機を使って、合成数から素数を見つける方法（素因数分解）を知りたいので、ご存知の方教えてください。 できれば、計算機科学における現在、最速の素因数分解の方法（アルゴリズム）を知りたいです。
- ベストアンサー
- 数学・算数
- 1111111の素因数分解
1111111という1が並ぶ数の中でも少ない桁数のものが、4649(よろしく)で割り切れることを知り、大変興味深く感じました。そこで1111111=239×4649という素因数分解を工夫してできないかを考えています。イメージ的には、例えば9991の素因数分解なら100^2－3^2と変形することで因数分解公式から103×97と分解できる、という具合です。何卒お知恵拝借いただきたく存じます。
- ベストアンサー
- 数学・算数
- 素因数分解をこの問題でどう使うのか？？
問題 「a、b、cは自然数とする。 2^3a×3^2b×5^cで表せる６桁の数があり、その中央の４桁は０７３６であることがわかっているとき、a,b,cの値を求めよ。」 これは中学生の問題です。私は家庭教師をしているのですが、情けないことにこの問題がわかりません。この問題のテーマは「素因数分解の利用」ということなのですが、どう素因数分解を利用するのかわかりません。 ～私の解法（素因数分解の利用なし）～ 3^2b＝９の倍数なので、９の倍数の性質と２×５＝１０を利用して６桁の数が「２０７３６０」とわかったのですが、素因数分解を利用していないので、この解法ではないと思います。そもそも９の倍数の性質を知らないと解けない問題自体見たことがありません。 素因数分解を利用する解法がわかる方はぜひ教えて下さい。お願いします。
- ベストアンサー
- 数学・算数
お礼
そうですか・・今現在最良の素因数分解のアルゴリズムの計算量を計算してみて納得したいと思います。 ありがとうございました。