素因数分解はなぜ困難？

質問

今暗号について勉強しています。その中に素因数分解が困難であることを利用してつくられた暗号がいくつかありますが、なぜ素因数分解が困難であるのかがわかりません。それを証明する方法などがありましたらなんでもいいので教えてください。

回答No.2

terra5 · ベストアンサー

素因数分解は結局可能性のある素数でつぎつぎと割ってみて、割り切れるかどうかで調べるしか手段なないこと。
この方法だと,桁数が増えたときに計算量が爆発的に増えることによります。

ただし、証明はまだされていないと思います。
ですから数学的には未解決の問題です。

証明は出来ませんが、ある桁数の数をある方法で素因数分解するための平均的な計算量などは計算できますから、
現在の最速の計算機で何億年もかかるとなると、
事実上解読不能ということになります。
もちろん、桁数が多くても2の倍数なんてつかったら、
あっという間に解かれますね(^^;

将来簡単な計算法が見付かる可能性も0ではありませんが、
過去の例からするとこういう問題はできないことが証明されるのがほとんどのようです。

お礼

そうですか・・今現在最良の素因数分解のアルゴリズムの計算量を計算してみて納得したいと思います。
ありがとうございました。

回答No.1

ADEMU

以下のサイトが参考になるでしょうか。
http://www.maitou.gr.jp/rsa/rsa14.html

補足

ありがとうございます。なんとなく困難であるということはわかりましたが、はっきり困難であるとういう数学的証明はできないのでしょうか？