Abstract
This brief presents a new hardware-efficient bit- parallel circuit for computing C + AB2 in finite fields GF(2m) over the canonical basis. It consists of two parts: a normal power-sum part and modular-reduction part, where each part is realized in a binary XOR tree structure. The proposed power-sum circuit works for the general-form generating polynomial and requires 3m2 -2m AND gates and 3m2 -4m + 2 XOR gates to reach low time complexity of O(log2 m). As compared to the conventional cellular-array structures for C + AB2 in GF(2""), the proposed one involves less hardware complexity and achieves a significant reduction in time complexity. The hardware requirement can further be reduced when a special-form generating polynomial is adopted. The corresponding reduced structures based on three special-form generating polynomials, including the trinomial xm + x + 1, the all-one polynomial, and the equally spaced polynomial, are given to demonstrate this property. A versatile structure, which can be programmed to compute inverses/divisions and exponentiations in GF(2""), is also constructed based on the proposed power-sum circuit. © 2000 IEEE.