• 締切済み
  • 暇なときにでも

素因数分解について

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

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

  • 回答数5
  • 閲覧数546
  • ありがとう数1

みんなの回答

  • 回答No.5

> で、素因数分解はNP完全なんです。 なぜここだけ間違いを? 素因数分解は回答例が与えられた場合、多項式時間でその回答が正しいか確認できるが、回答を多項式時間で得るアルゴリズムは存在を知られていない。 素因数分解はNP問題ではあるが、NP完全であるとは証明されていないようです

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

  • 回答No.4

 素因数分解は、計算に手間が掛かる。その背景を少しご紹介致します。  「計算理論」という数学の分野がありまして、いろいろなアルゴリズムの相互の関係ですとか、計算の手間について詳しく調べられています。この理論に於いて「易しい問題」とされるのは、データの量(つまりビット数)をnとするとき、nの何乗かに比例する手間で処理できる問題で、多項式(polynomial)時間の問題と呼ばれます。n^100000なんてのは現実問題として飛んでもなく手間が掛かる訳ですけれど、それでも易しい部類とみなされる。で、難しい問題てのはe^nに比例する手間がかかる。  さて、「問題を解くのにはe^nに比例する手間が掛かるけれど、答を教えて貰って、それが正しいかどうか検算するだけなら多項式時間でできる」という種類の問題は、non-deterministic polynimial(NP)時間の問題と呼ばれます。そして、非常に多くの重要なアルゴリズムが、NP問題に該当しています。  「NP問題を多項式時間で計算するアルゴリズムが存在するかどうか」というのが大問題でして、これは何十年間多くの人がトライして、YESともNOとも答が出ていません。しかし「できっこねーだろ、んなこと」というのが圧倒的大勢の意見ではあります。  また、NP問題の中には、「もしこの問題が多項式時間で計算できるなら、他のNP問題も全部多項式時間で計算できる」と証明されている問題があり、この性質をNP完全(non-deterministic polynimial complete)と言います。  で、素因数分解はNP完全なんです。だから、素因数分解を多項式時間でやれるアルゴリズムを見つけたら、「できっこねーだろ、んなこと」をひっくり返し、全てのNP問題が多項式時間で解けるようになる。大変なことです。フィールズ賞ぐらいじゃおっつかない、世界中の賞という賞を差し上げたい大発見です。  逆に言えば、素因数分解に基づく暗号化は安全だろう、と信じるに足るわけですね。

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

  • 回答No.3
noname#24477
noname#24477

人間なら、たとえば2003は素数かどうか確かめよ といわれたら ちょっと嫌になると思いますがやれないことはない。 50ぐらいまで確かめればいいですから。 しかし 2^17+1 ぐらいになったらお手上げで、 これはもうコンピュータの世界でしょう。 もっと大きくすればコンピュータでも嫌になるのは 前の方の説明のとおりです。

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

  • 回答No.2

大きい素数を掛け合わせた数字を素因数分解するのが技術的に難しいというわけではなく単純に「時間がかかる」のです。 RSAが現在推奨している鍵長1024ビットとは、10進数で言えば1.8x10の38乗、という数値です。 #1の方もおっしゃっておられるように、素因数分解するためには今のところ「素直に割り算」するしかありません。コンピュータにとって、割り算は苦手な計算です。この割り算を、ほとんど総当りでやっていかなければならないわけです。 予断ですが、これを「総当りでやらなくてもいい方法」をもし貴方が思いつかれたら、それはフィールズ賞(数学のノーベル賞)モノです。 しかも、一般的なCPUでは64ビット・128ビットといった数値の計算であれば簡単にできるようになっているのですが(このため、一時128ビットの鍵は危ない、などといわれていました)1024ビットの演算となるとプログラムを組んでやらなければなりません。 平たく言うと「すごく時間がかかる」わけです。 どれくらい時間がかかるというと、今推奨されている1024ビットの前の512ビットの鍵長ですら「252台のコンピュータを使って、5.2ヶ月かかった」そうです。 1024ビットでは単純にこれの2倍ではなく、2の512乗倍(≒1.34x10の154乗倍)の時間がかかることになります。 10の154乗倍ということですから、今5.2ヶ月として、5.8x10の153乗年、580兆年の100兆倍の100兆倍の100兆倍の100兆倍の100兆倍の・・・(100兆倍が9回続く)の1000倍の時間がかかることになります。

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

  • 回答No.1
  • qcelp
  • ベストアンサー率38% (20/52)

素因数分解は普通、小さい素数から順に割り切れるか試して割り切れなかったら次の小さい素数へって感じで計算していきます。 割り切れる素数がものすごく大きい場合、この計算回数が同様にものすごく多くなります。また、1回の割り切れるかどうかの計算も複雑になります。 そのため、大きな数の素因数分解は難しくなります。

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

関連するQ&A

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

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

  • 素因数分解はなぜ困難?

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

  • 素因数分解について

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

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

    問題 「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に168をかけると、ある数の二乗になりました。この整数nはいくらになるかという問題です。 168を素因数分解し、n×168=n×2^3×3×7となることは分かります。 これから先、どのように組み立てて解けばよいのか分かりません。 解説では、各素数が偶数個になるように解くと書かれており、ある数の二乗になるため、 n=2×3×7×m^2となっていました。 どうしてこのような式なるのですか? A=A^p×b^q×c^rとなっている時、各指数がすべて偶数(2の倍数)なっていれば、Aは何かの二乗になることは確かめてみました。

  • 素因数分解について

    中学三年で習う素因数分解についてです。 素因数分解をするときに、数字を最小の素数で割らなければいけない理由は何ですか? また、素因数分解を利用して最大公約数と最小公倍数を求めるための式(共通の素数をかけていくという式です)の意味が理解できません。。 何故あの式で最小公倍数と最大公約数が出るんでしょうか? テストが近いのでかなり焦っています。 どなたか詳しく説明してくださる方、回答よろしくお願いします。

  • 素数の素因数分解

    素数(例えば17)の素因数分解について  (1)すでに素因数分解は終わっている (17の素因数分解は17)  (2)素因数分解はできない のどちらの見解が正しいですか?

  • 素因数分解 解き方

    素因数分解 解き方 120=2X2X2X3X5  ←どうやってこの数が出てきたんですか? 3 =2 x3x7ってどうやったらこうなるんですか?  今、素数をマスターできましたが素因数分解はまだです。   詳しくお願いします!

  • 2通りの素因数分解

    素因数分解は一意に決まると学びましたが、大学時代にある数は2通りの素因数分解が出来ると聞いたような気がします。 私の記憶違いなのでしょうか?そんな数はあるのでしょうか?

  • 素因数分解について

    多分、すごく初歩的な質問だと思いますが、次のことは正しいですか? 1と素数以外の整数は、すべて素因数分解できる。 よろしくお願いします。