解決済み

素因数分解はなぜ困難?

  • すぐに回答を!
  • 質問No.208775
  • 閲覧数332
  • ありがとう数1
  • 気になる数0
  • 回答数2
  • コメント数0

お礼率 66% (2/3)

 今暗号について勉強しています。その中に素因数分解が困難であることを利用してつくられた暗号がいくつかありますが、なぜ素因数分解が困難であるのかがわかりません。それを証明する方法などがありましたらなんでもいいので教えてください。
通報する
  • 回答数2
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.2
レベル13

ベストアンサー率 34% (574/1662)

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

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

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

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

お礼率 66% (2/3)

 そうですか・・今現在最良の素因数分解のアルゴリズムの計算量を計算してみて納得したいと思います。
ありがとうございました。
投稿日時 - 2002-01-30 23:46:05

その他の回答 (全1件)

  • 回答No.1
レベル14

ベストアンサー率 31% (726/2280)

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

お礼率 66% (2/3)

ありがとうございます。なんとなく困難であるということはわかりましたが、はっきり困難であるとういう数学的証明はできないのでしょうか?
投稿日時 - 2002-01-30 22:45:49

このQ&Aで解決しましたか?
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する

特集


専門家があなたの悩みに回答!

ピックアップ

ページ先頭へ