| 講演名 | 2001/6/22 Steinのアルゴリズムに基づく有限体上の除算アルゴリズム 渡辺 恭章, 高木 直史, 高木 一義, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 有限体上の除算を行うVLSI実現向きのアルゴリズムを提案する.2整数の最大公約数を求めるSteinのアルゴリズムを2つの多項式の最大公約多項式を求めるように変更し,さらに,有限体上の除算を行うように拡張する.GF(2^m)上の除算がビットシフトやビット毎の排他的論理和演算などの単純な操作の繰り返しで行える.提案アルゴリズムに基づく回路は,規則正しいビットスライス構造を持ち,VLSI実現に適している.回路は高々2mクロックサイクルで演算を終了する.回路のゲート数はmに比例し,ゲート段数はmに依存しない. |
| 抄録(英) | A VLSI algorithm for division on finite fields with the polynomial basis representation is proposed. Stein's algorithm for integer GCD computation is modified to polynomiaI GCD computation and extended to division on finite fields. Division on GF (2^m) is carried out through iteration of simple operations, such as shifts and additions on GF (2^m). A divider on GF (2^m) based on the algorithm has a linear array structure with a bit-slice feature and carries out division in at most 2m clock cycles. The number of gates in the circuit is proportional to m and the depth of the circuit is independent of m. |
| キーワード(和) | 有限体上の除算 / 有限体上の逆元計算 / ハードウェアアルゴリズム / VLSIアルゴリズム / 公開鍵暗号 |
| キーワード(英) | multiplicative inversion on finite fields / division on finite fields / hardware algorithm / VLSI algorithm / public-key cryptosystem |
| 資料番号 | CAS2001-42,VLD2001-59,DSP2001-61 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2001/6/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Steinのアルゴリズムに基づく有限体上の除算アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An Algorithm for Division on Finite Fields Based on Stein's Algorithm |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 有限体上の除算 / multiplicative inversion on finite fields |
| キーワード(2)（和/英） | 有限体上の逆元計算 / division on finite fields |
| キーワード(3)（和/英） | ハードウェアアルゴリズム / hardware algorithm |
| キーワード(4)（和/英） | VLSIアルゴリズム / VLSI algorithm |
| キーワード(5)（和/英） | 公開鍵暗号 / public-key cryptosystem |
| 第 1 著者 氏名（和/英） | 渡辺 恭章 / Yasuaki Watanabe |
| 第 1 著者 所属（和/英） | 名古屋大学大学院工学研究科情報工学 Graduate School of Engineering, Nagoya University |
| 第 2 著者 氏名（和/英） | 高木 直史 / Naofumi Takagi |
| 第 2 著者 所属（和/英） | 名古屋大学大学院工学研究科情報工学 Graduate School of Engineering, Nagoya University |
| 第 3 著者 氏名（和/英） | 高木 一義 / Kazuyoshi Takagi |
| 第 3 著者 所属（和/英） | 名古屋大学大学院工学研究科情報工学 Graduate School of Engineering, Nagoya University |
| 発表年月日 | 2001/6/22 |
| 資料番号 | CAS2001-42,VLD2001-59,DSP2001-61 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 144 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |