プロが教えるわが家の防犯対策術!

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

教えて!goo グレード

A 回答 (5件)

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



なぜここだけ間違いを?

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

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

その背景を少しご紹介致します。
 「計算理論」という数学の分野がありまして、いろいろなアルゴリズムの相互の関係ですとか、計算の手間について詳しく調べられています。この理論に於いて「易しい問題」とされるのは、データの量(つまりビット数)を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問題が多項式時間で解けるようになる。大変なことです。フィールズ賞ぐらいじゃおっつかない、世界中の賞という賞を差し上げたい大発見です。
 逆に言えば、素因数分解に基づく暗号化は安全だろう、と信じるに足るわけですね。
    • good
    • 0

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


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

しかし 2^17+1 ぐらいになったらお手上げで、
これはもうコンピュータの世界でしょう。
もっと大きくすればコンピュータでも嫌になるのは
前の方の説明のとおりです。
    • good
    • 0

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


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倍の時間がかかることになります。
    • good
    • 0

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


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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

教えて!goo グレード

人気Q&Aランキング