アカウント名:
パスワード:
もし元の素数が素数であることが (たとえばパソコンレベルで) 簡単に分かるのなら、かけあわせた結果できる巨大な数も、その気になれば (たとえばスーパーコンピュータを使って) 簡単に素因数分解できてしまうような気がします。
ここにとある数字 102210419 があります。 これを素因数分解するには、最大で √102210419 (≒10109)まで割り算してやる必要があります。 実はこの数字 102210419 は5桁の最初の素数 10069 と、次の素数 10151 をかけたものなのですが、10069 が素数である事を確認するためには √10069 (≒100)まで割り算してやれば済みます。 2つの数字を確認するにしても、その2倍の200回割り算してやれば良い訳で、1万回対200回という事で50倍の計算量の差になります。
数字が大きくなればこの計算量の差はもっと開いてきます。 たとえば、5桁の最大の素数 99971 と、その一つ前 99839 をかけた 9981004669 で考えれば、√9981004669(≒99904)と √99971(≒316)で158倍(99904/(316*2))の計算量です。
この計算量の差が、キモなのです。
素因数分解の計算回数をNとすると、 分解された因数が素数であることを判定するための平均的な計算回数は およそN^(1/2)であるという説明をしているようですが、 それだと素数判定はNP問題であるということになります。
そして、2つの素数の積からできる大きな数Nを素因数分解することと 素数判定することの計算量は同じという説明にもなっています。
で御指摘の親コメントの論法の問題点ですが、特定の問題の複雑さを 示すのに、始めに手法を与えて、その手法の手間を問題にしている 部分で、その手法を選んだ妥当性について論じていません。 これは問題だと思います。
まず#451173のACさんへ。 平均的な計算回数がN^(1/2)ではなく、最大でN^(1/2)だと言っています。Boldで。
次にsakamotoさんへもですが、#450511では数学的な証明をしている訳でも、検証をしている訳でもありません。 「素人」向けに素因数分解と、その因数が素数である事の検証には計算量に多くの差があるという事を直感的に理解させる事を目的としていま
素因数分解をするには、与えられた数から素因数を一つ見つける必要があります。 もし、素因数の候補が見つかったら、それが与えられた数の素因数かどうかは、 実際に割算をすればチェックできます(このように答が正しいかのチェックが 容易にできる問題をNP問題とか言います)。従って、素因数分解の難しさは 実際の割算ではなく、与えられた数から素因数の候補を見つけることにあります。 現在、量子コンピュータを使用しない限りは、この候補を見つける効率の良い 方法はわかってません。複雑な数論を使わない限り、1 から与えられた数 の平方根のうちのどれか位しかわかりません(複雑な数論を使っても 与えられた数の桁数個程度まで絞りこむことはできてません)。 従って、与えられる数が10倍になる(桁が一桁増える)と、候補の数は数個増える どころではなく、数倍に膨れ上がります。このように桁が増えるにつれ、計算の 手間が数倍になっていくような計算を指数時間と言います。
一方、素数に関しては、様々な定理が成り立つことが知られています。 素数にしか成り立たない定理に合成数を代入するとおかしなことになります。 このような定理の例としては、素数 p に対して、任意の数のp-1乗したものを pで割ると余りが 1 になる(フェルマーの小定理)などがあります。 特に群論に関する定理に対しては、おかしなことが発生すると集合のサイズが 1/2 以下になってしまうことがわかっています。 この性質をうまく利用すると、与えられた数が 素数かどうかをチェックする式を桁数(の何乗か)に比例した数程度に絞る ことができるようになります。 与えた数の桁数の何乗かに計算の手間が比例する計算を多項式時間とか P とか 言います。 # 行数はなんとかなったけど、分量はちょっと多めかな? 素数判定まで おまけにつけたので許して下さい
あなたの文章は「理解させるため」ではなく「教えるため」のものですね。 言っている事は数学的には正しいかもしれませんが、『「素数」というのは、その数と1以外では割り切れない数』程度の知識の人が「理解」できるものではありません。 たとえば、フェルマーの小定理など、そこで示されれば「ふ~ん。そういうのがあるのか」と知る事はできますが理解できるような説明ではないですね。 理解していない事を元に計算量に差がある事を示されても、それは理解したのではなく知ったに過ぎません。
もう一つおまけに言っておけば、暗号に素因数分解を使って
自戒ですか? 他人に誤解だとか言うのなら、まず原論文にでも当たってください。 RSAなどでは、まず「素数」ありきで話は始まります。 その「素数」をどうやって作るかとか、そういう斟酌無しに「素数」がまず存在し、それを元に「鍵」を知っている人には容易に復号できるが「鍵
一方 Primarity in P の論文を読むと、今までの積み重ねから とうとうできたかという感想を持ちました。 超天才というよりは日頃の鍛錬の成果なのかなぁと思いました。
sakamoto さんの記事の丸かっこ内に書いてあるとおり、「誤る可能性はあるけど高速なアルゴリズム」を使ってたのですよ。
# もちろん確定的なテストも使ってますが、あまりに遅いものは使ってないと思います。 # トリビアですが、確率的な素数テストを通過してしまう合成数を「擬素数」と呼びます。
決定性の多項式時間で判定できるのは、そんなのは紀元前から出来ていますよ。ただ遅かっただけで。
またこういう嘘を平気で書くもんなあ。モデレートダウンもされてないし。元のコメントでリンクされている論文の冒頭にもはっきりと
In 1983, Adleman, Pomerance, and Rumely achieved a major breakthrough by giving a deterministic algorithm for primality that runs in (log n)O(log log log n) time (all the previous deterministic algorithms required expon
決定性の多項式時間で判定できるのは、そんなのは紀元前から出来ていますよ。ただ遅かっただけで。 またこういう嘘を平気で書くもんなあ。
またこういう嘘を平気で書くもんなあ。
そう考えれば、x=2^n-1が素数かどうか判定するのにO(2^n)かかるアルゴリズムも、多項式時間アルゴリズムということになってしまいますからね。
すいません、 (log n)O(log log log n)って O(log n) にはならないのですか?
そんなのは紀元前から出来ていますよ を肯定しているのでしょうか???
たとえば、3からsqrt(n)までのすべての奇数で割ってみるという 一番素朴なアルゴリズムの計算量は、割り算が定数時間としてO(n^0.5)となります。ここで問題のサイズとしてnそのものをとれば、この素朴アルゴリズムは立派な多項式時間アルゴリズムと解釈できるわけです。
しかし常識的にはln nをサイズとして考えるべきなので、そうすると計算量はO(2^((ln n)/2))となり、桁数の指数関数となります。
また、暗号を送る際、平文となる数は、合成数と互いに素でなければなりません。 平文の定義域が連続している場合、最小の素因数よりも小さい値までの 範囲までしか送ることができません。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
にわかな奴ほど語りたがる -- あるハッカー
素人の質問 (スコア:0)
もし元の素数が素数であることが (たとえばパソコンレベルで) 簡単に分かるのなら、かけあわせた結果できる巨大な数も、その気になれば (たとえばスーパーコンピュータを使って) 簡単に素因数分解できてしまうような気がします。
Re:素人の質問 (スコア:5, 参考になる)
ここにとある数字 102210419 があります。
これを素因数分解するには、最大で √102210419 (≒10109)まで割り算してやる必要があります。
実はこの数字 102210419 は5桁の最初の素数 10069 と、次の素数 10151 をかけたものなのですが、10069 が素数である事を確認するためには √10069 (≒100)まで割り算してやれば済みます。
2つの数字を確認するにしても、その2倍の200回割り算してやれば良い訳で、1万回対200回という事で50倍の計算量の差になります。
数字が大きくなればこの計算量の差はもっと開いてきます。
たとえば、5桁の最大の素数 99971 と、その一つ前 99839 をかけた 9981004669 で考えれば、√9981004669(≒99904)と √99971(≒316)で158倍(99904/(316*2))の計算量です。
この計算量の差が、キモなのです。
Re:素人の質問 (スコア:0)
> たとえば、5桁の最大の素数 99971 と、その一つ前 99839 をかけた 9981004669 で考えれば、
> √9981004669(≒99904)と√99971(≒316)で158倍(99904/(316*2))の計算量です。
>
> この計算量の差が、キモなのです。
素因数分解の計算回数をNとすると、
分解された因数が素数であることを判定するための平均的な計算回数は
およそN^(1/2)であるという説明をしているようですが、
それだと素
Re:素人の質問 (スコア:1)
で御指摘の親コメントの論法の問題点ですが、特定の問題の複雑さを 示すのに、始めに手法を与えて、その手法の手間を問題にしている 部分で、その手法を選んだ妥当性について論じていません。 これは問題だと思います。
-- 哀れな日本人専用(sorry Japanese only) --
Re:素人の質問 (スコア:0)
まず#451173のACさんへ。
平均的な計算回数がN^(1/2)ではなく、最大でN^(1/2)だと言っています。Boldで。
次にsakamotoさんへもですが、#450511では数学的な証明をしている訳でも、検証をしている訳でもありません。
「素人」向けに素因数分解と、その因数が素数である事の検証には計算量に多くの差があるという事を直感的に理解させる事を目的としていま
Re:素人にわかるようにチャレンジ!!! (スコア:1)
素因数分解をするには、与えられた数から素因数を一つ見つける必要があります。 もし、素因数の候補が見つかったら、それが与えられた数の素因数かどうかは、 実際に割算をすればチェックできます(このように答が正しいかのチェックが 容易にできる問題をNP問題とか言います)。従って、素因数分解の難しさは 実際の割算ではなく、与えられた数から素因数の候補を見つけることにあります。 現在、量子コンピュータを使用しない限りは、この候補を見つける効率の良い 方法はわかってません。複雑な数論を使わない限り、1 から与えられた数 の平方根のうちのどれか位しかわかりません(複雑な数論を使っても 与えられた数の桁数個程度まで絞りこむことはできてません)。 従って、与えられる数が10倍になる(桁が一桁増える)と、候補の数は数個増える どころではなく、数倍に膨れ上がります。このように桁が増えるにつれ、計算の 手間が数倍になっていくような計算を指数時間と言います。
一方、素数に関しては、様々な定理が成り立つことが知られています。 素数にしか成り立たない定理に合成数を代入するとおかしなことになります。 このような定理の例としては、素数 p に対して、任意の数のp-1乗したものを pで割ると余りが 1 になる(フェルマーの小定理)などがあります。 特に群論に関する定理に対しては、おかしなことが発生すると集合のサイズが 1/2 以下になってしまうことがわかっています。 この性質をうまく利用すると、与えられた数が 素数かどうかをチェックする式を桁数(の何乗か)に比例した数程度に絞る ことができるようになります。 与えた数の桁数の何乗かに計算の手間が比例する計算を多項式時間とか P とか 言います。
# 行数はなんとかなったけど、分量はちょっと多めかな? 素数判定まで おまけにつけたので許して下さい
-- 哀れな日本人専用(sorry Japanese only) --
Re:素人にわかるようにチャレンジ!!! (スコア:0)
知識があるがゆえに「量子コンピュータを使用しない限りは」とか
「複雑な数論を使わない限り」などといった余計なことまで書いて
しまうんだろうね。素人向けなんだからそういうことは不要。
あと「指数時間」と「多項式時間」も不要なんじゃないかなぁ。
名称よりも概念
素人の意見 (スコア:0)
#450511の方が数字の具体例が出ている分、よっぽどわかりやすくて親切だ。
Re:素人にわかるようにチャレンジ!!! (スコア:0)
あなたの文章は「理解させるため」ではなく「教えるため」のものですね。
言っている事は数学的には正しいかもしれませんが、『「素数」というのは、その数と1以外では割り切れない数』程度の知識の人が「理解」できるものではありません。
たとえば、フェルマーの小定理など、そこで示されれば「ふ~ん。そういうのがあるのか」と知る事はできますが理解できるような説明ではないですね。
理解していない事を元に計算量に差がある事を示されても、それは理解したのではなく知ったに過ぎません。
もう一つおまけに言っておけば、暗号に素因数分解を使って
Re: 理解と誤解 (スコア:0)
> 単により良い、長い鍵が簡単に作れるようになるというだけの事
まさにここでしょう。
そもそも、#450487 のAC氏の素人の素朴な疑問ってのは、
「素数判定と素因数分解に「どの程度」計算量の差があるんだろう?
素数
Re: 理解と誤解 (スコア:0)
自戒ですか?
他人に誤解だとか言うのなら、まず原論文にでも当たってください。
RSAなどでは、まず「素数」ありきで話は始まります。
その「素数」をどうやって作るかとか、そういう斟酌無しに「素数」がまず存在し、それを元に「鍵」を知っている人には容易に復号できるが「鍵
Re:素人の質問 (スコア:2, 参考になる)
-- 哀れな日本人専用(sorry Japanese only) --
Re:素人の質問 (スコア:1)
逆は証明されてなかったような。
すなわち、何らかの画期的な方法を使えば素因数分解せずとも
RSAを解ける可能性がないことは否定されてなかったような。
# まぁこれもあまたの数学者が挑戦してきたことだと思うので
# 超天才でもない限りちょっとした気合や根性ではできないと思うけど。
Re:素人の質問 (スコア:1)
一方 Primarity in P の論文を読むと、今までの積み重ねから とうとうできたかという感想を持ちました。 超天才というよりは日頃の鍛錬の成果なのかなぁと思いました。
-- 哀れな日本人専用(sorry Japanese only) --
Re:素人の質問 (スコア:0)
Re:素人の質問 (スコア:1, 興味深い)
sakamoto さんの記事の丸かっこ内に書いてあるとおり、「誤る可能性はあるけど高速なアルゴリズム」を使ってたのですよ。
# もちろん確定的なテストも使ってますが、あまりに遅いものは使ってないと思います。
# トリビアですが、確率的な素数テストを通過してしまう合成数を「擬素数」と呼びます。
Re:素人の質問 (スコア:0)
Re:素人の質問 (スコア:0)
またこういう嘘を平気で書くもんなあ。モデレートダウンもされてないし。元のコメントでリンクされている論文の冒頭にもはっきりと
Re:素人の質問 (スコア:1)
そう考えれば、x=2^n-1が素数かどうか判定するのにO(2^n)かかるアルゴリズムも、多項式時間アルゴリズムということになってしまいますからね。
Re:素人の質問 (スコア:0)
すいません、 (log n)O(log log log n)って O(log n) にはならないのですか?
O(log n)なら桁数って思えるのですが。
あと、
> そう考えれば、x=2^n-1が素数かどうか判定するのにO(2^n)かかるアルゴリズムも、
> 多項式時間アルゴリズムということになってしまいますからね。
と書いているということは、
> 決定性の多項式時間で判定できるのは、そんなのは紀元前から出来ていますよ
を肯定しているのでしょうか???
例えば通常の10進数で考えて(2進数にしても基本的には
Re:素人の質問 (スコア:1)
たとえば、3からsqrt(n)までのすべての奇数で割ってみるという 一番素朴なアルゴリズムの計算量は、割り算が定数時間としてO(n^0.5)となります。ここで問題のサイズとしてnそのものをとれば、この素朴アルゴリズムは立派な多項式時間アルゴリズムと解釈できるわけです。
しかし常識的にはln nをサイズとして考えるべきなので、そうすると計算量はO(2^((ln n)/2))となり、桁数の指数関数となります。
Re:素人の質問 (スコア:0)
正しいのは(log n)^O(log log log n)です。だからO(log n)にはなりません。準指数関数時間であって多項式時間ではありません。
2002年?1983年?どっち (スコア:0)
ちょっとお願い (スコア:0)
モデレータのほとんどは専門知識を持っていませんし、
英語に堪能なわけでもありません。
大多数は一般的な人たちです。
あなたのような専門家にコメントの形で
補完していただければ助かります。
また、わたしも自分の専門分野については
補完するつもりです。
Re:素人の質問 (スコア:0)
素人な答え (スコア:0)
「素因数分解」は
「素数かどうか判定する」ことに比べてずっと大変で、
「素因数分解」は桁が2倍程度に増えるだけで、非常に時間がかかる。
ということから、暗号が成立する
(大きな2つの素数を見つけることはできるが、
そのような数をかけたものはちょっとやそっとじゃ
因数分解できない)
のではないかと。
何倍? (スコア:0)
> 「素因数分解」は
> 「素数かどうか判定する」ことに比べてずっと大変で、
> 「素因数分解」は桁が2倍程度に増えるだけで、非常に時間がかかる。
桁が2倍に増えたら、処理時間は何倍になるのですか?
「桁が2倍に増えた
Re:何倍? (スコア:0)
「この非常に時間ががかるというのは、これくらいなんですよ」
とあなたが補足すればいいのに。
答え (スコア:0)
約 e^(1.93(log 2*x)^(1/3)(log (log 2*x))^(2/3))/e^(1.93(log x)^(1/3)(log (log x))^(2/3)) 倍(x:元の数の桁数)
ぐらい(間違ってるかも)ですが、この値って、説明にほんとに必要?
Re:答え (スコア:0)
e^(1.93(log 1024)^(1/3)(log (log 1024))^(2/3)) = 303.8
e^(1.93(log 2048)^(1/3)(log (log 2048))^(2/3)) = 442.7
1024桁を倍の2048桁にしても、高々1.5倍にしかなんないよ。いくら桁を増やしても、あっと言う間に素因数分解できそうだね。
Re:答え (スコア:0)
Re:答え (スコア:0)
その説明によって「非常に増える」が間違いであることが分かった
Re:素人の質問 (スコア:0)
RSAを使う時は、そもそもこれをする必要がないのでは?
素因数分解が用いられている理由は、鍵の長さがながくなると指数関数的に解読に手間がかかるためです。
Re:素人の質問 (スコア:1)
また、暗号を送る際、平文となる数は、合成数と互いに素でなければなりません。 平文の定義域が連続している場合、最小の素因数よりも小さい値までの 範囲までしか送ることができません。
-- 哀れな日本人専用(sorry Japanese only) --
Re:素人の質問 (スコア:0)
素数でないものを使うとブルートフォースに対する耐性が格段に落ちますから。
ただ、確認していると長い時間がかかってしまうので、確率的な方法で「良さそうな値」を探して代用しているだけ。
Re:素人の質問 (スコア:0)
Re:素人の質問 (スコア:0)
どのくらいの容量が必要なんですかねぇ。
その気になればできるものなのだろうか?
# この前 600 万桁超のが見つかったしなぁ…
Re:素人の質問 (スコア:0)
1,000,000,000,000,000(1エクサ)までの素数だと28,952,965,460,216(約28ペタ)個。
今回の576bit(十進174桁)にも全然足らないですが、その気になってもかなり難しいかと。