| 講演名 | 2007-03-09 拡張ユークリッド法に基づくGF(2^m)上の乗算・逆元計算のための複合回路(演算回路/専用回路,システムオンシリコン設計技術並びにこれを活用したVLSI) 小林 克希, 高木 直史, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | GF(2^m)上の乗算及び逆元計算のための複合回路を提案する.提案回路は,これまでに提案されている複合回路と異なり,構成がGF(2^m)を定義する既約多項式に依存せず,また,入出力される多項式の係数の順序を反転する必要がない.提案回路において,逆元計算は拡張ユークリッド法に,乗算はMSB-firstアルゴリズムに基づいており,それぞれのアルゴリズムの類似性に着目して回路の大部分を共用できるように複合した.複合には乗算と逆元計算で剰余多項式の次数が同一である必要があるため,乗算の場合の剰余多項式を変形して次数を揃え,他の変数もその変形に合わせた.提案回路を論理合成して回路の規模を見積もったところ,面積はそれぞれの回路を別々に持つよりも4割程度小さかった. |
| 抄録(英) | A combined circuit for multiplication and inversion in GF(2^m) is proposed. In contrast with previously proposed combined circuits, the proposed circuit does not depend on the irreducible polynomial that defined the field nor need to reverse the order of the coefficients of inputs and putput polynomials. In the proposed combined circuit, multiplication is based on MSB-first algorithm and inversion is based on the extended Euclid's algorithm. To share almost all hardware components of the circuit for multiplication and inversion, we combine these algorithms by focusing similarity between those. Since the degrees of reduction polynomials in multiplication and inversion needs to be identical, we modify the reduction polynomial of multiplication to satisfy the condition. Additionally, we adjust other variables to this modification. The area of the proposed circuit has been estimated by logic synthesis. The area of the proposed circuit is about 40% smaller than the total area of ordinary multiplication circuit and inversion circuit. |
| キーワード(和) | ガロア体 / GF(2^m) / 乗算 / 逆元計算 / 拡張ユークリッド法 |
| キーワード(英) | Galois field / GF(2^m) / multiplication / inversion / extended Euclid's algorithm |
| 資料番号 | VLD2006-142,ICD2006-233 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2007/3/2(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 拡張ユークリッド法に基づくGF(2^m)上の乗算・逆元計算のための複合回路(演算回路/専用回路,システムオンシリコン設計技術並びにこれを活用したVLSI) |
| サブタイトル（和） | |
| タイトル（英） | A Combined Circuit for Multiplication and Inversion in GF(2^m) Based on the Extended Euclid's Algorithm |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ガロア体 / Galois field |
| キーワード(2)（和/英） | GF(2^m) / GF(2^m) |
| キーワード(3)（和/英） | 乗算 / multiplication |
| キーワード(4)（和/英） | 逆元計算 / inversion |
| キーワード(5)（和/英） | 拡張ユークリッド法 / extended Euclid's algorithm |
| 第 1 著者 氏名（和/英） | 小林 克希 / Katsuki KOBAYASHI |
| 第 1 著者 所属（和/英） | 名古屋大学大学院情報科学研究科情報システム学専攻 Department of Information Engineering, Graduate School of Information Science, Nagoya University |
| 第 2 著者 氏名（和/英） | 高木 直史 / Naofumi TAKAGI |
| 第 2 著者 所属（和/英） | 名古屋大学大学院情報科学研究科情報システム学専攻 Department of Information Engineering, Graduate School of Information Science, Nagoya University |
| 発表年月日 | 2007-03-09 |
| 資料番号 | VLD2006-142,ICD2006-233 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 549 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |