パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

RSA-576が素因数分解される」記事へのコメント

  • by Anonymous Coward
    素因数分解がそんなに難しいのなら、かけあわせる元となるふたつの素数が素数であるということを確認することも、難しいのではないでしょうか?

    もし元の素数が素数であることが (たとえばパ

    • Re:素人の質問 (スコア:5, 参考になる)

      by Anonymous Coward
      素人にもわかりやすいように、多少ゴマ化しながら説明しましょう。

      ここにとある数字 102210419 があります。
      これを素因数分解するには、最大で √102210419 (≒10109)まで割り算してやる必要があります。
      実はこの数字 102210419 は5桁の最初の素数 10069 と、次の素数 10151 をかけたものなのですが、10069 が素数である事を確認するためには √10069 (≒100)まで割り算してやれば済みます。
      2つの数字を確認するにしても、その2倍の200回割り算してやれば良い訳で、1万回対200回という事で

      • by Anonymous Coward on 2003年12月09日 15時35分 (#451173)
        > 数字が大きくなればこの計算量の差はもっと開いてきます。
        > たとえば、5桁の最大の素数 99971 と、その一つ前 99839 をかけた 9981004669 で考えれば、
        > √9981004669(≒99904)と√99971(≒316)で158倍(99904/(316*2))の計算量です。
        >
        > この計算量の差が、キモなのです。

        素因数分解の計算回数をNとすると、
        分解された因数が素数であることを判定するための平均的な計算回数は
        およそN^(1/2)であるという説明をしているようですが、
        それだと素数判定はNP問題であるということになります。

        そして、2つの素数の積からできる大きな数Nを素因数分解することと
        素数判定することの計算量は同じという説明にもなっています。

        この2点に関しては「多少ゴマ化し」と言えないほど
        大きな間違いを含んでいるようですが、いかがなものでしょうか。
        親コメント
        • by sakamoto (8009) on 2003年12月09日 16時52分 (#451232) 日記
          素因数分解の計算回数をNとすると、 分解された因数が素数であることを判定するための平均的な計算回数は およそN^(1/2)であるという説明をしているようですが、 それだと素数判定はNP問題であるということになります。
          これはNP問題の定義を根本的に誤解されているような気がします。 ここは素朴な手法に固定すると指数時間の計算量になると言うだけの主張 です。
          そして、2つの素数の積からできる大きな数Nを素因数分解することと 素数判定することの計算量は同じという説明にもなっています。
          実際、もっとも素朴な素数判定は、エラトステネスのふるいをやることで、 それには目的の数の平方根までの数で割算する必要があります。

          で御指摘の親コメントの論法の問題点ですが、特定の問題の複雑さを 示すのに、始めに手法を与えて、その手法の手間を問題にしている 部分で、その手法を選んだ妥当性について論じていません。 これは問題だと思います。

          --
          -- 哀れな日本人専用(sorry Japanese only) --
          親コメント
          • by Anonymous Coward
            #450511のACです。

            まず#451173のACさんへ。
            平均的な計算回数がN^(1/2)ではなく、最大でN^(1/2)だと言っています。Boldで。

            次にsakamotoさんへもですが、#450511では数学的な証明をしている訳でも、検証をしている訳でもありません。
            「素人」向けに素因数分解と、その因数が素数である事の検証には計算量に多くの差があるという事を直感的に理解させる事を目的としていま

            • では、御要望にお応えして……

              素因数分解をするには、与えられた数から素因数を一つ見つける必要があります。 もし、素因数の候補が見つかったら、それが与えられた数の素因数かどうかは、 実際に割算をすればチェックできます(このように答が正しいかのチェックが 容易にできる問題をNP問題とか言います)。従って、素因数分解の難しさは 実際の割算ではなく、与えられた数から素因数の候補を見つけることにあります。 現在、量子コンピュータを使用しない限りは、この候補を見つける効率の良い 方法はわかってません。複雑な数論を使わない限り、1 から与えられた数 の平方根のうちのどれか位しかわかりません(複雑な数論を使っても 与えられた数の桁数個程度まで絞りこむことはできてません)。 従って、与えられる数が10倍になる(桁が一桁増える)と、候補の数は数個増える どころではなく、数倍に膨れ上がります。このように桁が増えるにつれ、計算の 手間が数倍になっていくような計算を指数時間と言います。

              一方、素数に関しては、様々な定理が成り立つことが知られています。 素数にしか成り立たない定理に合成数を代入するとおかしなことになります。 このような定理の例としては、素数 p に対して、任意の数のp-1乗したものを pで割ると余りが 1 になる(フェルマーの小定理)などがあります。 特に群論に関する定理に対しては、おかしなことが発生すると集合のサイズが 1/2 以下になってしまうことがわかっています。 この性質をうまく利用すると、与えられた数が 素数かどうかをチェックする式を桁数(の何乗か)に比例した数程度に絞る ことができるようになります。 与えた数の桁数の何乗かに計算の手間が比例する計算を多項式時間とか P とか 言います。
              # 行数はなんとかなったけど、分量はちょっと多めかな? 素数判定まで おまけにつけたので許して下さい

              --
              -- 哀れな日本人専用(sorry Japanese only) --
              親コメント
              • 正直わかりづらい。#450511 の方がよいデキだと思う。

                知識があるがゆえに「量子コンピュータを使用しない限りは」とか
                「複雑な数論を使わない限り」などといった余計なことまで書いて
                しまうんだろうね。素人向けなんだからそういうことは不要。

                あと「指数時間」と「多項式時間」も不要なんじゃないかなぁ。
                名称よりも概念
              • by Anonymous Coward
                何を言ってるのかさっぱりわからん。
                #450511の方が数字の具体例が出ている分、よっぽどわかりやすくて親切だ。
              • #450511のACです。

                あなたの文章は「理解させるため」ではなく「教えるため」のものですね。
                言っている事は数学的には正しいかもしれませんが、『「素数」というのは、その数と1以外では割り切れない数』程度の知識の人が「理解」できるものではありません。
                たとえば、フェルマーの小定理など、そこで示されれば「ふ~ん。そういうのがあるのか」と知る事はできますが理解できるような説明ではないですね。
                理解していない事を元に計算量に差がある事を示されても、それは理解したのではなく知ったに過ぎません。

                もう一つおまけに言っておけば、暗号に素因数分解を使って

              • by Anonymous Coward
                暗号に素因数分解が使える理由の一番のキモは、単なる計算量の差などではなく、
                > 単により良い、長い鍵が簡単に作れるようになるというだけの事
                まさにここでしょう。

                そもそも、#450487 のAC氏の素人の素朴な疑問ってのは、
                「素数判定と素因数分解に「どの程度」計算量の差があるんだろう?
                    素数
              • by Anonymous Coward
                ># 理解した気分になってる人は、単に誤解しているだけに過ぎない

                自戒ですか?
                他人に誤解だとか言うのなら、まず原論文にでも当たってください。
                RSAなどでは、まず「素数」ありきで話は始まります。
                その「素数」をどうやって作るかとか、そういう斟酌無しに「素数」がまず存在し、それを元に「鍵」を知っている人には容易に復号できるが「鍵

※ただしPHPを除く -- あるAdmin

処理中...