素因数分解について

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

No.5 回答者： yasush_sapporo 回答日時： 2010/07/25 09:34

>　で、素因数分解はNP完全なんです。

なぜここだけ間違いを？

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

No.4 回答者： stomachman 回答日時： 2004/02/07 23:48

　素因数分解は、計算に手間が掛かる。

その背景を少しご紹介致します。
　「計算理論」という数学の分野がありまして、いろいろなアルゴリズムの相互の関係ですとか、計算の手間について詳しく調べられています。この理論に於いて「易しい問題」とされるのは、データの量（つまりビット数）を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 回答日時： 2004/02/02 00:39

人間なら、たとえば２００３は素数かどうか確かめよ

といわれたら
ちょっと嫌になると思いますがやれないことはない。
５０ぐらいまで確かめればいいですから。

しかし　２＾１７＋１　ぐらいになったらお手上げで、
これはもうコンピュータの世界でしょう。
もっと大きくすればコンピュータでも嫌になるのは
前の方の説明のとおりです。

No.2 回答者： daibutsuda 回答日時： 2004/02/01 23:09

大きい素数を掛け合わせた数字を素因数分解するのが技術的に難しいというわけではなく単純に「時間がかかる」のです。

ＲＳＡが現在推奨している鍵長１０２４ビットとは、１０進数で言えば１．８ｘ１０の３８乗、という数値です。
＃１の方もおっしゃっておられるように、素因数分解するためには今のところ「素直に割り算」するしかありません。コンピュータにとって、割り算は苦手な計算です。この割り算を、ほとんど総当りでやっていかなければならないわけです。

予断ですが、これを「総当りでやらなくてもいい方法」をもし貴方が思いつかれたら、それはフィールズ賞（数学のノーベル賞）モノです。

しかも、一般的なＣＰＵでは６４ビット・１２８ビットといった数値の計算であれば簡単にできるようになっているのですが（このため、一時１２８ビットの鍵は危ない、などといわれていました）１０２４ビットの演算となるとプログラムを組んでやらなければなりません。

平たく言うと「すごく時間がかかる」わけです。
どれくらい時間がかかるというと、今推奨されている１０２４ビットの前の５１２ビットの鍵長ですら「２５２台のコンピュータを使って、５．２ヶ月かかった」そうです。
１０２４ビットでは単純にこれの２倍ではなく、２の５１２乗倍（≒１．３４ｘ１０の１５４乗倍）の時間がかかることになります。
１０の１５４乗倍ということですから、今５．２ヶ月として、５．８ｘ１０の１５３乗年、５８０兆年の１００兆倍の１００兆倍の１００兆倍の１００兆倍の１００兆倍の・・・（１００兆倍が９回続く）の１０００倍の時間がかかることになります。

No.1 回答者： qcelp 回答日時： 2004/02/01 22:19

素因数分解は普通、小さい素数から順に割り切れるか試して割り切れなかったら次の小さい素数へって感じで計算していきます。

割り切れる素数がものすごく大きい場合、この計算回数が同様にものすごく多くなります。また、１回の割り切れるかどうかの計算も複雑になります。
そのため、大きな数の素因数分解は難しくなります。