講演抄録/キーワード |
講演名 |
2007-03-09 09:20
拡張ユークリッド法に基づくGF(2^m)上の乗算・逆元計算のための複合回路 ○小林克希・高木直史(名大) エレソ技報アーカイブへのリンク:ICD2006-233 |
抄録 |
(和) |
$\mathrm{GF}(2^m)$上の乗算及び逆元計算のための
複合回路を提案する.
提案回路は,これまでに提案されている複合回路と異なり,
構成が$\mathrm{GF}(2^m)$を定義する既約多項式に依存せず,
また,入出力される多項式の係数の順序を反転する必要がない.
提案回路において,逆元計算は拡張ユークリッド法に,
乗算はMSB-firstアルゴリズムに基づいており,
それぞれのアルゴリズムの類似性に着目して
回路の大部分を共用できるように複合した.
複合には乗算と逆元計算で剰余多項式の次数が同一である必要があるため,
乗算の場合の剰余多項式を変形して次数を揃え,
他の変数もその変形に合わせた.
提案回路を論理合成して回路の規模を見積もったところ,
面積はそれぞれの回路を別々に持つよりも$4$割程度小さかった. |
(英) |
A combined circuit for multiplication and inversion in
$\mathrm{GF}(2^m)$ is proposed.
In contrast with previously proposed combined circuits,
the proposed circuit does not depend on the irreducible polynomial
that defines the field
nor need to reverse the order of the coefficients of inputs and
output 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. |
キーワード |
(和) |
ガロア体 / 乗算 / 逆元計算 / 拡張ユークリッド法 / / / / |
(英) |
Galois field / multiplication / inversion / extended Euclid's algorithm / / / / |
文献情報 |
信学技報, vol. 106, no. 549, VLD2006-142, pp. 13-18, 2007年3月. |
資料番号 |
VLD2006-142 |
発行日 |
2007-03-02 (VLD, ICD) |
ISSN |
Print edition: ISSN 0913-5685 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
エレソ技報アーカイブへのリンク:ICD2006-233 |