2024-03-29T00:18:54Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000166182020-10-27T05:02:43Z00934:00935:00954:00956
モンゴメリ乗算法の高速化High Performance Montgomery Multiplicationjpn発表概要http://id.nii.ac.jp/1001/00016618/Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=16618&item_no=1&attribute_id=1&file_no=1Copyright (c) 2005 by the Information Processing Society of Japan東京工業大学情報理工学研究科東京工業大学情報理工学研究科国立情報学研究所情報基盤研究系東京工業大学情報理工学研究科テイチョユウ太田昌孝松本, 尚荒木, 純道モンゴメリ乗算法は高速な剰余乗算法の1 つである.一方,レジスタブロッキング手法やキャリーセーブ手法などは多倍長乗算に有効であることが知られている.本研究では,これらの手法を多倍長演算に対応するモンゴメリ乗算法に実装した.Intel 社のItanium2(900MHz)とPentium4(2.2 GHz)上のC 言語実装で,従来型多倍長モンゴメリ乗算法と高速化された多倍長モンゴメリ乗算法の処理速度を比較した.Itanium2(900MHz)上の44 160 ビット剰余乗算に対して,高速型の処理速度は従来型より約8.37 倍が得られた.Pentium4(2.2 GHz)上の11 520 ビット剰余乗算に対して,高速型の処理速度は従来型より約2.16 倍が得られた.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.AA11464814情報処理学会論文誌プログラミング(PRO)46SIG11(PRO26)70702005-08-151882-78022009-06-30