• ベストアンサー
  • すぐに回答を!

素因数分解はなぜ困難?

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

共感・応援の気持ちを伝えよう!

  • 回答数2
  • 閲覧数425
  • ありがとう数1

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

  • ベストアンサー
  • 回答No.2
  • terra5
  • ベストアンサー率34% (574/1662)

素因数分解は結局可能性のある素数でつぎつぎと割ってみて、割り切れるかどうかで調べるしか手段なないこと。 この方法だと,桁数が増えたときに計算量が爆発的に増えることによります。 ただし、証明はまだされていないと思います。 ですから数学的には未解決の問題です。 証明は出来ませんが、ある桁数の数をある方法で素因数分解するための平均的な計算量などは計算できますから、 現在の最速の計算機で何億年もかかるとなると、 事実上解読不能ということになります。 もちろん、桁数が多くても2の倍数なんてつかったら、 あっという間に解かれますね(^^; 将来簡単な計算法が見付かる可能性も0ではありませんが、 過去の例からするとこういう問題はできないことが証明されるのがほとんどのようです。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

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

その他の回答 (1)

  • 回答No.1
  • ADEMU
  • ベストアンサー率31% (726/2280)

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

共感・感謝の気持ちを伝えよう!

質問者からの補足

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

関連するQ&A

  • 素因数分解について

     ものすごく大きな素数二つを掛け合わせた数を素因数分解することは難しい、というようなことを本で読みました。 これって暗号を作ることにも利用されているみたいですが、どうしてこの数を素因数分解することが難しいのでしょうか?

  • 素因数分解をこの問題でどう使うのか??

    問題 「a、b、cは自然数とする。 2^3a×3^2b×5^cで表せる6桁の数があり、その中央の4桁は0736であることがわかっているとき、a,b,cの値を求めよ。」 これは中学生の問題です。私は家庭教師をしているのですが、情けないことにこの問題がわかりません。この問題のテーマは「素因数分解の利用」ということなのですが、どう素因数分解を利用するのかわかりません。 ~私の解法(素因数分解の利用なし)~ 3^2b=9の倍数なので、9の倍数の性質と2×5=10を利用して6桁の数が「207360」とわかったのですが、素因数分解を利用していないので、この解法ではないと思います。そもそも9の倍数の性質を知らないと解けない問題自体見たことがありません。 素因数分解を利用する解法がわかる方はぜひ教えて下さい。お願いします。

  • 素因数分解の証明問題

    素因数分解の証明問題 証明方法がわかりません。 自然数の素因数分解をn=(P_1)^e_1(p_2)^e_2・・・(p_r)^e_rとする。このとき、 φ(n)=n{1-(1/p_1)}{1-(1/p_2)}・・・{1-(1/p_r)}となることを示せ。 ただし、自然数m,nに対して、gcd(m,n)=1ならば、φ(mn)=φ(m)φ(n)であることを用いよ。 よろしくお願いします。

  • 素因数分解

    X4乗+4を素因数分解してください。また文字のついているものを素因数分解する方法を教えてください。

  • 素因数分解

    全ての自然数は、素因数分解出来るのでしょうか? また、出来る場合は、それが証明されているのでしょうか?

  • すばやく素因数分解する方法は?

    「暗号解読」(サイモン・シン(著)青木薫(訳) 新潮社)という本を読んで、急に素数のことに関心を持ちました。 数十桁もある数(合成数)を素因数分解するのは、えらく時間がかかることが書かれていました。 中学生が計算する素因数分解や、「エラトステネスのふるい」のほかに、手計算や計算機を使って、合成数から素数を見つける方法(素因数分解)を知りたいので、ご存知の方教えてください。 できれば、計算機科学における現在、最速の素因数分解の方法(アルゴリズム)を知りたいです。

  • 素因数分解について

    X=√4,840,000 を素因数分解?? で解く場合、100*2*11=2,200 となると思いますが、素数の100を1000にしては駄目ですか? そもそも、素因数分解のルールが理解出来ていません。 素因数分解の簡単なやり方を分かり易く教えて下さる方、宜しくお願いいたします。 因数分解は方程式なので、取っ付きにくいイメージがあります。

  • 素因数分解ができない?

    123、205の最大公約数はいくつでしょう? 素因数分解をして求めたいのですが、 123は3で割って41 3* 205は5で割って41 5* となるのでしょうか? その後の素因数分解が続きません。 すいませんが、教えてください。 よろしくお願いします。

  • 1を素因数分解しなさい

    数学的には例外(素因数分解できない)は作りたくないのですが…。 でも、「1」の素因数分解と言われたら、答はどうなるのでしょう。

  • 素因数分解する問題?

    √1980B の根号がとれる最も小さい自然数Bを求めよ。 上の問題で たぶん素因数分解をすると思うのですが、 素因数分解してそのあとがよくわかりません こんな私にもわかるように説明してほしいです; よろしくお願いします。