A low time-complexity, hardware-efficient bit-parallel power-sum circuit for finite fields GF(2M)

This paper presents a new hardware-efficient bit-parallel circuit for computing C+AB² over finite fields GF(2^M) with the canonical basis representation. The circuit consists of two parts-normal power-sum part and modular reduction part, where each part is realized in a binary XOR tree structure. It works for the general form generating polynomial and requires 3m²-2m AND gates and 3m²-4m+2 XOR gates to reach low time complexity of O(log₂m). As compared to the conventional cellular-array structures for the same problem, the proposed one involves less hardware complexity and achieves a significant reduction in time complexity. Note that 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