A 回答 (5件)
- 最新から表示
- 回答順に表示
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
- 回答日時:
人間なら、たとえば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
- 回答日時:
素因数分解は普通、小さい素数から順に割り切れるか試して割り切れなかったら次の小さい素数へって感じで計算していきます。
割り切れる素数がものすごく大きい場合、この計算回数が同様にものすごく多くなります。また、1回の割り切れるかどうかの計算も複雑になります。
そのため、大きな数の素因数分解は難しくなります。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
100以下の自然数のうち、次のよ...
-
エクセル関数で源泉徴収額を計...
-
ラプラス変換の「s」とは?
-
エクセルで60進法計算の仕方...
-
平均アップ率を求める方法
-
三角形の計算
-
中3の問題です
-
○進法とかの計算方法。
-
工事の共通仮設費率の計算がで...
-
端数を習うのは小学何年生の頃...
-
Excelで勤務の過不足時間を計算...
-
この産み分けの計算でハズレの...
-
関数電卓の使い方
-
10分の1は「10/1 それとも1/10...
-
実績を積むという表現
-
【機械図面】 最大値・最小値...
-
50以下は“50”も入るのですか?
-
1億x1億はいくらでしょうか?
-
5進法を10進法への直し方
-
アクセスのデータ型。数値型に...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
100以下の自然数のうち、次のよ...
-
エクセルで60進法計算の仕方...
-
エクセル関数で源泉徴収額を計...
-
工事の共通仮設費率の計算がで...
-
この産み分けの計算でハズレの...
-
エクセルでのシグマ計算
-
3桁の自然数の中で、次の個数を...
-
Excelで勤務の過不足時間を計算...
-
ラプラス変換の「s」とは?
-
○+○=5
-
経費率の計算方法を教えて下さい。
-
勝率50%の事象を100回やって勝...
-
最小公倍数と最大公約数の求め...
-
99の10乗の下位5桁の数を求める...
-
端数を習うのは小学何年生の頃...
-
文字を含む三角関数の定積分の...
-
X-0.3X=Y でYを求めるには?
-
◯ヶ月を△年◇月というように変換...
-
数学というより算数なのですが...
-
ローン支払いにおける金利の計...
おすすめ情報