アカウント名:
パスワード:
もし元の素数が素数であることが (たとえばパ
ここにとある数字 102210419 があります。 これを素因数分解するには、最大で √102210419 （≒10109）まで割り算してやる必要があります。 実はこの数字 102210419 は5桁の最初の素数 10069 と、次の素数 10151 をかけたものなのですが、10069 が素数である事を確認するためには √10069 （≒100）まで割り算してやれば済みます。 2つの数字を確認するにしても、その2倍の200回割り算してやれば良い訳で、1万回対200回という事で
素因数分解の計算回数をNとすると、 分解された因数が素数であることを判定するための平均的な計算回数は およそN^(1/2)であるという説明をしているようですが、 それだと素数判定はNP問題であるということになります。
これは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などでは、まず「素数」ありきで話は始まります。 その「素数」をどうやって作るかとか、そういう斟酌無しに「素数」がまず存在し、それを元に「鍵」を知っている人には容易に復号できるが「鍵
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
アレゲは一日にしてならず -- アレゲ見習い
素人の質問 (スコア:0)
もし元の素数が素数であることが (たとえばパ
Re:素人の質問 (スコア:5, 参考になる)
ここにとある数字 102210419 があります。
これを素因数分解するには、最大で √102210419 （≒10109）まで割り算してやる必要があります。
実はこの数字 102210419 は5桁の最初の素数 10069 と、次の素数 10151 をかけたものなのですが、10069 が素数である事を確認するためには √10069 （≒100）まで割り算してやれば済みます。
2つの数字を確認するにしても、その2倍の200回割り算してやれば良い訳で、1万回対200回という事で
Re:素人の質問 (スコア:0)
> たとえば、5桁の最大の素数 99971 と、その一つ前 99839 をかけた 9981004669 で考えれば、
> √9981004669（≒99904）と√99971（≒316）で158倍（99904/(316*2)）の計算量です。
>
> この計算量の差が、キモなのです。
素因数分解の計算回数をNとすると、
分解された因数が素数であることを判定するための平均的な計算回数は
およそN^(1/2)であるという説明をしているようですが、
それだと素
Re:素人の質問 (スコア:1)
これはNP問題の定義を根本的に誤解されているような気がします。 ここは素朴な手法に固定すると指数時間の計算量になると言うだけの主張 です。
-- 哀れな日本人専用(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などでは、まず「素数」ありきで話は始まります。
その「素数」をどうやって作るかとか、そういう斟酌無しに「素数」がまず存在し、それを元に「鍵」を知っている人には容易に復号できるが「鍵