A low-complexity power-sum circuit for GF(2m) and its applications

This brief presents a new hardware-efficient bit- parallel circuit for computing C + AB(2) in finite fields GF(2(m)) 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 3m(2) - 2m AND gates and 3m(2) - 4m + 2 XOR gates to reach low time complexity of O(log(2) m). As compared to the conventional cellular-array structures for C + AB(2) in GF(2(m)),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 x(m) + 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(m)), is also constructed based on the proposed power-sum circuit.