| 講演名 | 2003/7/10 太田乗算法にレジスタブロッキングやキャリーセーブ手法の適用に関する研究 テイ チョユウ, 太田 昌孝, 荒木 純道, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | キャリーの伝搬をまとめて行うキャリーセーブ手法は高速ハードウェア乗算器で使われる伝統的な技法であり、レジスタブロッキングは行列の乗算の高速なコーディング手法であるが、太田は両手法が多倍長乗算にも有効であることを示した。本研究では多倍長乗算に基づく剰余乗算法である太田乗算法にキャリーセーブとレジスタブロッキング手法を適用して実験し、一方,剰余乗算のモンゴメリ乗算法にも従来知られてきた最適の方式に基づく効率的なコーディングを採用しIntel社のPentium4(1.8GHz)のプロセッサ上で両者の性能を比較した.C言語によるコーディングで220bitの剰余乗算に対して,太田乗算法は1.74μs計算時間,モンゴメリ乗算法は1.79μsの計算時間が得られ、太田乗算法はモンゴメリ乗算法より約3%高速になった.作成したプログラムは,公開鍵暗号特に楕円暗号の計算に必要な程度の桁数に対して有効性と期待できる。 |
| 抄録(英) | Carry save technique, which delays propagations of carries, is a classical technique for fast hardware multiplication and register blocking technique is a efficient coding technique for matrix multiply, both of which was shown by Ohta to be applicable to multiprecision multiplication. In this paper, effectiveness of carry save and register blocking techniques for Ohta Multiplication, which is a modular multiplication using multiprecision multiplications, is compared against Montgomery Multiplication with most efficient coding known so far on Intel Pentium4 (1.8GHz) processor. For 220 bits of modular multiplication coded with C, Ohta Multiplication and Montogomery one take 1.74us and 1.79us, correspondingly, that Ohta Multiplication is about 3% faster than Montgomery one. The program is expected to be applicable to computations of public key cryptography, esiecially Elliptic one. |
| キーワード(和) | 太田乗算法 / モンゴメリ乗算法 / 剰余乗算 / レジスタブロッキング / キャリーセーブ / ハイパフオーマンスコンピューティング / 楕円暗号 / RSA暗号 |
| キーワード(英) | Ohta method / Montgomery method / modular multiplication / Register Blocking / Carry Save / High Performance Computing / Elliptic Curve Cryptography / RSA Cryptography |
| 資料番号 | ISEC2003-17 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2003/7/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 太田乗算法にレジスタブロッキングやキャリーセーブ手法の適用に関する研究 |
| サブタイトル（和） | |
| タイトル（英） | Research on the applications of Register Blocking Technique and Carry Save Technique to Ohta Method |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 太田乗算法 / Ohta method |
| キーワード(2)（和/英） | モンゴメリ乗算法 / Montgomery method |
| キーワード(3)（和/英） | 剰余乗算 / modular multiplication |
| キーワード(4)（和/英） | レジスタブロッキング / Register Blocking |
| キーワード(5)（和/英） | キャリーセーブ / Carry Save |
| キーワード(6)（和/英） | ハイパフオーマンスコンピューティング / High Performance Computing |
| キーワード(7)（和/英） | 楕円暗号 / Elliptic Curve Cryptography |
| キーワード(8)（和/英） | RSA暗号 / RSA Cryptography |
| 第 1 著者 氏名（和/英） | テイ チョユウ / Chuyur ZHENG |
| 第 1 著者 所属（和/英） | 東京工業大学情報理工学研究科 Graduate School of Information Science and Engineering, Tokyo Institute of Technology |
| 第 2 著者 氏名（和/英） | 太田 昌孝 / Masataka OHTA |
| 第 2 著者 所属（和/英） | 東京工業大学情報理工学研究科 Graduate School of Information Science and Engineering, Tokyo Institute of Technology |
| 第 3 著者 氏名（和/英） | 荒木 純道 / Kiyomichi ARAKI |
| 第 3 著者 所属（和/英） | 東京工業大学理工学研究科 Graduate School of Science and Engineering, Tokyo Institute of Technology |
| 発表年月日 | 2003/7/10 |
| 資料番号 | ISEC2003-17 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 195 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |