講演名 | 2002/11/21 剰余系乗除算回路 KAIHARA Marcelo E., 高木 直史, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | VLSI実現向きの剰余系乗除算回路を提案する.乗算はモンゴメリ乗算法、除算は拡張バイナリアルゴリズムに基づく.両方の演算ともビットシフトや加減算などの単純な操作の繰り返しで行う.基数2の符号付きディジット表現を用いることにより全ての加減算を桁上げ伝播なしに行う.提案する剰余系乗除算回路は,規則正しいビットスライス構造を持ち,nビットの剰余系乗算及び除算をO(n)クロックサイクルで演算を実行する。クロックサイクルの長さはnに依存しない. |
抄録(英) | We propose a modulo M multiplier/divider which is suitable for VLSI realization. It is based on our newly proposed combined algorithm for modular multiplication and division. The modular multiplication is based on Montgomery's method and the modular division on the extended Binary GCD algorithm. Both calculations are carried out through iteration of simple operations such as shifts and addition/subtractions. The radix-2 signed-digit representation is employed so that all additions and subtractions are performed without carry propagation. The modulo M multiplier/divider has a linear array structure with a bit-slice feature and carries out n-bit modulo M multiplication/division in O(n) clock cycles, where the length of the clock cycle is constant and independent of n. |
キーワード(和) | 剰余系演算 / 剰余乗算 / 剰余除算 / モンゴメリアルゴリズム / 拡張バイナリGCDアルゴリズム / ハードウェアアルゴリズム / VLSIアルゴリズム |
キーワード(英) | modular arithmetic / modular multiplication / modular division / Montogomery's algorithm / extended binary GCD algorithm / hardware algorithm / VLSI algorithm |
資料番号 | VLD2002-109 |
発行日 |
研究会情報 | |
研究会 | VLD |
---|---|
開催期間 | 2002/11/21(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | VLSI Design Technologies (VLD) |
---|---|
本文の言語 | ENG |
タイトル(和) | 剰余系乗除算回路 |
サブタイトル(和) | |
タイトル(英) | A Modulo M Multiplier/Divider |
サブタイトル(和) | |
キーワード(1)(和/英) | 剰余系演算 / modular arithmetic |
キーワード(2)(和/英) | 剰余乗算 / modular multiplication |
キーワード(3)(和/英) | 剰余除算 / modular division |
キーワード(4)(和/英) | モンゴメリアルゴリズム / Montogomery's algorithm |
キーワード(5)(和/英) | 拡張バイナリGCDアルゴリズム / extended binary GCD algorithm |
キーワード(6)(和/英) | ハードウェアアルゴリズム / hardware algorithm |
キーワード(7)(和/英) | VLSIアルゴリズム / VLSI algorithm |
第 1 著者 氏名(和/英) | KAIHARA Marcelo E. / Marcelo E. KAIHARA |
第 1 著者 所属(和/英) | 名古屋大学大学院工学研究科情報工学 Department of Information Engineering, Nagoya University |
第 2 著者 氏名(和/英) | 高木 直史 / Naofumi TAKAGI |
第 2 著者 所属(和/英) | 名古屋大学大学院工学研究科情報工学 Department of Information Engineering, Nagoya University |
発表年月日 | 2002/11/21 |
資料番号 | VLD2002-109 |
巻番号(vol) | vol.102 |
号番号(no) | 476 |
ページ範囲 | pp.- |
ページ数 | 6 |
発行日 |