パスワードを忘れた？ アカウント作成
Close
3587 story

素数判定アルゴリズムを開発 22

ストーリー by yourCat
堰が切れるか? 部門より

moonbear曰く、"Indian Institute of Technology KanpurのManindra Agrawal教授らのグループが多項式時間で素数判定ができるアルゴリズムを開発したそうです。論文もあります (Peer review等がされているのかどうか定かではないのですが)。これは素数判定であって素因数分解ではないので、実際に今使っている暗号のアルゴリズムがすぐにだめになるわけではないのですが。"

このネタはいくつかタレコミがあったが、暗号への影響を懸念したものが多かった。実際の所どうなんだろうか。

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

素数判定アルゴリズムを開発 More

  • 決定的に、ってことが重要 (スコア:2, 参考になる)

    by saitoh (10803) on 2002年08月09日 22時27分 (#143319)
    確率的に素数判定をするアルゴリズムは以前から知られて いるので、これのキーポイントはdeterministicという ことですね。

    暗号に関しては、公開鍵暗号の鍵を作るのが楽になる？ 素因数分解がこれまでより易しくなるとはおもえないけど (あまり深く検討せずに書いてます).

    • そうみたいですね．私も数論はよくわかっていないので論文をちゃんと読んではいないのですが，アルゴリズムを見る限り，合成数だと判定される場合に入力の素因数がわかるような情報はなさそうです（あったらもっと大騒ぎになっていると思います）．
      シェア
      親コメント

  • 映画「CUBE」を思い出す (スコア:1)

    by stiletto (5594) on 2002年08月11日 2時02分 (#143815)
    オフトピで失礼。
    映画「CUBE」 [cubethemovie.com]を思い出しました。
    登場人物の1人のカザンという男が、頭脳のみでバリバリ素数の計算をやっていく姿が爽快でした。
    CUBEの細かいシステムはここ [asahi-net.or.jp]が参考になります。

    #今や因数分解すらあやしいほど数学オンチの私。

  • エラトステネスの篩 (スコア:0)

    by Anonymous Coward on 2002年08月09日 22時55分 (#143333)
    　を馬鹿正直に N までやると O(N^2) ですけど。これも多項式時間?

    (defun prime-p (n)
      (let ((v (make-array (1+ n) :initial-element t)))
        (setf (aref v 0) nil)
        (setf (aref v 1) nil)
        (dotimes (i (1+ n))
          (when (aref v i)
            (do ((j (+ i i) (+ i j)))
                ((> i n))
              (setf (aref v j) nil))))
        (aref v n)))
    ;; C で書いたけど変な文字があるって云われるじゃん。

    • Re:エラトステネスの篩 (スコア:3, 参考になる)

      by moonbear (4602) on 2002年08月09日 23時42分 (#143373)
      ええと，こういう問題は桁数に対してどのくらいのオーダーになるかが重要なんだと思います．例えばnビットの数についてこのプログラムをそのまま適用すると，2^nに比例した記憶領域と時間がかかってしまいます．
      シェア
      親コメント
      • 基本的なことだと思うんですけど、こういう場合の四則演算 自体の速さってのは O(1) でいいんでしょうか? O(n) とかにしないと多倍長につかえないじゃん、っておもったり。
        # 掛け算は FFTで速くできる、とかきいたが。

        • Re:エラトステネスの篩 (スコア:3, 参考になる)

          by tix (7637) on 2002年08月10日 1時04分 (#143427) ホームページ
          d ビット整数の加減算は O(d) 時間です。乗算は素朴にやると O(d^2) 時間、 FFT を使った乗算では O(d log d log log d) 時間です。

          商と余りを求める除算の計算量はよく知りません。素朴には O(d^2) 時間でやっているように思いますが。
          --
          鵜呑みにしてみる？
          シェア
          親コメント

          • Re:エラトステネスの篩 (スコア:2, 参考になる)

            by K_O_ (7268) on 2002年08月11日 0時49分 (#143794)
            d bitの除算はNewton-Raphsonで近似計算すればケチらなくってもlog d回の乗算(と加減算)で終りますよ。余りを求める除算の場合だって多少後処理するだけで、同じオーダーでしょう。

            ちなみに各近似ステップでの有効桁数は倍々で伸びるので、必要充分な演算精度にして演算量をもっと減らすことは出来る筈です。

            でなきゃあそこまで莫大な円周率の計算なんてできません。
            シェア
            親コメント
            • d bitの除算はNewton-Raphsonで近似計算すればケチらなくってもlog d回の乗算(と加減算)で終りますよ。
              忘れていました。お恥ずかしい限りです。ということは、乗算に FFT を使えば除算のオーダは O(d log^2 d log log d) 時間まで落ちますね。ありがとうございます。
              --
              鵜呑みにしてみる？
              シェア
              親コメント
          • SRTならゲートの遅延が O(d) でできます．(アルゴリズムの計算量じゃありません，念のため)

            • Re:エラトステネスの篩 (スコア:2, 参考になる)

              by tix (7637) on 2002年08月10日 12時08分 (#143588) ホームページ
              「SRT」がわからなくて調べたら、 Sweeney-Robertson-Tocher の除算法、 non-restoring division （引き算の結果が負になってもそのまま計算を進めるような除算の方法？）を高速化したもの、と出てきました。 Pentium などでも使われているようですね。

              non-restoring division も初耳なので、 SRT 除算まで理解するのは大変そうです。
              --
              鵜呑みにしてみる？
              シェア
              親コメント
        • O(1)とO(n)の違いは今の場合はあまり重要ではないでしょうね。

    • Re:エラトステネスの篩 (スコア:2, 参考になる)

      by mishima (737) on 2002年08月09日 23時34分 (#143362) ホームページ 日記
      件の論文の Introduction には、エラトステネスのふるいの計算量は
      入力サイズの指数オーダだって書いてあるけど。
      んで、こっちのアルゴリズムの計算量は(漸近的には) O( log(n)^12 ) だって。
      --
      # mishimaは本田透先生を熱烈に応援しています
      シェア
      親コメント

  • 素因数分解もＰに入っている (スコア:0)

    by Anonymous Coward on 2002年08月10日 14時07分 (#143613)
    と専門家は思っているらしい。（今回の件に関するニュースでどこかで読んだ）

    量子コンピュータでできちゃうし、本物のＮＰハードよりは少し簡単だという感じがあるのだろうか。

    専門家の方、そのあたりの雰囲気はどうなんですか？
typodupeerror

一つのことを行い、またそれをうまくやるプログラムを書け -- Malcolm Douglas McIlroy