A New Architecture for a Parallel Finite Field Multiplier with Low Complexity Based on Composite Fields
A New Architecture for a Parallel Finite Field Multiplier with Low Complexity Based on Composite Fields
复制标题
DOI：
10.1109/12.508323
复制
发表时间：
1996-07
期刊：
影响因子：
--
通讯作者：
C. Paar
中科院分区：
文献类型：
--
作者：
C. Paar
本文介绍了一种低复杂度的位并行结构。乘法器在复合域GF（（2/sup n/）/sup m/）上操作，其中k=nm。Karatsuba-Ofman算法（A. Karatsuba和Y. Ofmanis，1963），并将其应用于GF（2/sup n/）上多项式的乘法。它表明，该操作的复杂性为O（k/suplog 23/）的顺序在一定的约束下，关于k。本文给出了一套完整的复合域的本原域多项式，它能以较低的复杂度进行模约简。结果，列出了具有低门计数和低延迟的域GF（2/sup k/）直到k=32的乘法器。该架构是高度模块化的，因此非常适合VLSI实现。
A bit parallel structure for a multiplier with low complexity in Galois fields is introduced. The multiplier operates over composite fields GF((2/sup n/)/sup m/), with k=nm. The Karatsuba-Ofman algorithm (A. Karatsuba and Y. Ofmanis, 1963) is investigated and applied to the multiplication of polynomials over GF(2/sup n/). It is shown that this operation has a complexity of order O(k/sup log23/) under certain constraints regarding k. A complete set of primitive field polynomials for composite fields is provided which perform module reduction with low complexity. As a result, multipliers for fields GF(2/sup k/) up to k=32 with low gate counts and low delays are listed. The architectures are highly modular and thus well suited for VLSI implementation.