| 講演名 | 2004/5/20 GF(2^m)上の逆元算出のための拡張ユークリッド法に基づくテーブルを用いたアルゴリズム(システム設計及び一般) 小林 克希, 高木 直史, 高木 一義, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では、GF(2^m)上の逆元算出のための拡張ユークリッド法に基づくテーブルを用いたアルゴリズムを提案する。提案アルゴリズムでは、従来の拡張ユークリッド法に基づく逆元算出アルゴリズムの数回`の反復における演算を行列で表現し、事前に計算してテーブルに保持しておく。これにより、提案アルゴリズムをハードウェア実装した際に、従来よりもXORの段数を削減するこ仁が可能となる.また、w×(w+1)ビットのGF(2^m)上の乗算器を用いれば、ソフトウェア実装した際に多倍長演算の処理時間を削減し、高速化することが可能である。 |
| 抄録(英) | In this paper, an algorithm using look-up table based on extended Euclid's algorithm for computing inversion in GF(2^m) is proposed. In this algorithm, operations corresponding to several contiguous iterations of the conventional algorithm are represented in an array. To speed up the computation, this array is precomputed and stored in a look-up table. An inverter in GF(2^m) based in this algorithm has a the number of XOR stages reduced. Moreover, the processing time of a multiple-precision inversion over GF(2^m) in software implementation can be reduced using a w × (w + l)-bit multiplier over GF(2^m). |
| キーワード(和) | ガロア体 / 拡張ユークリッド法 / 逆元 / テーブル |
| キーワード(英) | Galois field / extended Euclid's algorithm / inversion / look-up table |
| 資料番号 | VLD2004-2 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2004/5/20(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | GF(2^m)上の逆元算出のための拡張ユークリッド法に基づくテーブルを用いたアルゴリズム(システム設計及び一般) |
| サブタイトル（和） | |
| タイトル（英） | An Algorithm Using Look-Up Table Based on Extended Euclid's Algorithm for Computing Inversion in GF(2^m) |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ガロア体 / Galois field |
| キーワード(2)（和/英） | 拡張ユークリッド法 / extended Euclid's algorithm |
| キーワード(3)（和/英） | 逆元 / inversion |
| キーワード(4)（和/英） | テーブル / look-up table |
| 第 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 |
| 第 3 著者 氏名（和/英） | 高木 一義 / Kazuyoshi TAKAGI |
| 第 3 著者 所属（和/英） | 名古屋大学大学院情報科学研究科 Department of Information Engineering, Graduate School of Information Science, Nagoya University |
| 発表年月日 | 2004/5/20 |
| 資料番号 | VLD2004-2 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 78 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |