EFFICIENT MULTIPLIER ARCHITECTURES FOR GALOIS FIELDS GF(2(4N))

This contribution introduces a new class of multipliers for finite fie lds GF((2(n))(4)). The architecture is based on a modified version of the Karatsuba-Ofman algorithm (KOA). By determining optimized field po lynomials of degree four, the last stage of the KOA and the modulo red uction can be combined. This saves computation and area in VLSI implem entations. The new algorithm leads to architectures which show a consi derably improved gate complexity compared to traditional approaches an d reduced delay if compared with KOA-based architectures with separate module reduction. The new multipliers lead to highly modular architec tures and are, thus, well suited for VLSI implementations. Three types of field polynomials are introduced and conditions for their existenc e are established. For the small fields, where n = 2, 3,..., 8, which are of primary technical interest, optimized field polynomials were de termined by an exhaustive search. For each field order, exact space an d time complexities are provided.