モンゴメリ乗算法の高速化

• Item type: Trans(1)
• 公開日: 2005-08-15
• タイトル: モンゴメリ乗算法の高速化
• タイトル / 言語: en
• タイトル: High Performance Montgomery Multiplication
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 発表概要
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京工業大学情報理工学研究科
• 著者所属: 東京工業大学情報理工学研究科
• 著者所属: 国立情報学研究所情報基盤研究系
• 著者所属: 東京工業大学情報理工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Engineering Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Engineering Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Foundations of Informatics Research Division National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Engineering Tokyo Institute of Technology
• 著者名: テイチョユウ; 太田昌孝; 松本, 尚; 荒木, 純道
• 著者名(英): Zheng, Chuyu; Mastaka, Ohta; Takashi, Matsumoto; Kiyomichi, Araki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: モンゴメリ乗算法は高速な剰余乗算法の1 つである．一方，レジスタブロッキング手法やキャリーセーブ手法などは多倍長乗算に有効であることが知られている．本研究では，これらの手法を多倍長演算に対応するモンゴメリ乗算法に実装した．Intel 社のItanium2（900MHz）とPentium4（2.2 GHz）上のC 言語実装で，従来型多倍長モンゴメリ乗算法と高速化された多倍長モンゴメリ乗算法の処理速度を比較した．Itanium2（900MHz）上の44 160 ビット剰余乗算に対して，高速型の処理速度は従来型より約8.37 倍が得られた．Pentium4（2.2 GHz）上の11 520 ビット剰余乗算に対して，高速型の処理速度は従来型より約2.16 倍が得られた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Montgomery multiplication is a fast modular multiplication method. It is known that register blocking and carry save techniques etc. are effectively applied in multiprecision multiplications. In this research, we implemented the multiprecision Montgomery multiplication with these techniques. We make comparison of processing speed between original multiprecision Montgomery multiplication and improved multiprecision Montgomery multiplication on Intel Pentium4 (2.2 GHz) processor and Intel Itanium2 (900 MHz). For the implementation of Itanium2 (900 MHz) processor, it is obtainable that the processing speed of 44,160 bits of modular multiplication would be increased to 8.37 times as fast as original one. For the implementation of Pentium4 (2.2 GHz) processor, it is obtainable that the processing speed of 11,520 bits of modular multiplication would be increased to 2.16 times as fast as original one.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 46, 号 SIG11(PRO26), p. 70-70, 発行日 2005-08-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会