プログラミングの為の ..
[
2ch
|
▼Menu
]
■コピペモード
□
スレを通常表示
□
オプションモード
□このｽﾚｯﾄﾞのURL
■項目テキスト
604:デフォルトの名無しさん 06/12/22 12:31:04 >>601 RSA の乗算＋剰余演算の場合、FFT による方法じゃなくて、 Montgomery multiplication っていう高速化手法があるよ。 検証したことはないけど、2048 ビット程度では FFT の効果はない あるいは逆効果ってのはそうだと思う。 せめて1万ワードくらいの長さはないと。 605:デフォルトの名無しさん 06/12/22 12:37:35 ああ、あと、ワード長が2のべきになってる場合、 上位・下位半分ずつ、再帰的に計算することで 乗算回数減らす方法もある。 下位桁の乗算結果使って、上位桁の乗算をサボる。 昔、RSA のプログラムの最適化の仕事したことあるけど、 「単純に畳み込みで乗算 ＆ 引き放し法的な剰余」を 「再帰乗算 ＆ Montgomery 乗算法」に変えたら 鍵長256bitでも動作速度を250倍以上速くできた。 606:デフォルトの名無しさん 06/12/22 12:41:24 補足： 速度250倍達成は、あと、 バイト単位で多倍長整数演算してたのを、 1ワード32ビット単位に変えたのも含めてだわ。
次ページ
最新レス表示
スレッドの検索
類似スレ一覧
話題のニュース
おまかせリスト
▼オプションを表示
レスジャンプ
mixiチェック！
Twitterに投稿
オプション
しおりを挟む
スレッドに書込
スレッドの一覧
暇つぶし2ch
5385日前に更新/259 KB
担当:undef