A new architecture for a parallel finite field multiplier with low complexity based on composite fields

Abstract

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.