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

世界最速スパコンより 1000 倍速い分子コンピュータ」記事へのコメント

  • 桁数が多い処理解くのに便利そうだなー
    素数探査とか暗号解読に使えるんじゃね?

    • 変換結果を何百桁の精度で得られる訳じゃないと思うので、暗号解読にどれほど役に立つのか疑問です。
      偉い人、教えてください!

      • by Anonymous Coward on 2010年05月11日 12時01分 (#1761864)
        多倍長の計算をFFTでやるのは,よく知られたテクニックで,
        GNUMPなんかにも使われていたと思います.
        そういうわけで,大きい整数を扱う公開鍵暗号や,それに関連した素因数分解は
        速くなるんじゃないでしょうか.

        どうやって精度保証をしているのかは,理論があるらしいですが,
        詳しくは知りません.
        親コメント
        • by Anonymous Coward on 2010年05月11日 14時09分 (#1761985)
          >どうやって精度保証をしているのかは,理論があるらしいですが,
          >詳しくは知りません.
          FFTによる乗算の利用と精度の保障についてはPeter Henriciによる著ISBN-13: 978-0471608417にきっちりと書かれていたはずです。
          (私も大分昔に読んだので具体的になんだったか良く覚えていませんが^^;)

          さて、多倍精度整数の乗算ですが、現状では単純な平方による古典的乗算(2n^2)、Karatsuba法の再帰的適用(O(n^(log 3)))、Schönhage and Strassen (1971), Schönhage(1977), Cantor and Kaltofen (1991)のFFTによるアルゴリズム(O(n log n log log n))が一般的な様です。
          ただしO記法で見かけ上のオーダーが低く見積もれると言ってもアルゴリズムは複雑になる傾向にあり、コストが極端なものにならない限り単純な古典的方法やKaratsuba法が処理速度が有利な場合があります。
          波束エンジニアリングに関してはよく分かりませんが、今回の記事を見る限り複雑な処理もより低コストに実装できるようになり、昔から知られていた単純なものと、オーダーは低いが複雑で遅いものとの差が一層小さくなるのではないでしょうか。
          親コメント
        • by Anonymous Coward

          ビット数を増やすとレーザー装置もたくさん要る
          というオチ?

犯人はmoriwaka -- Anonymous Coward

処理中...