and Its Applications
Jyh-Huei Guo, Chin-Liang Wang · 2000
This brief presents a new hardware-efficient bit- parallel cir- cuit for computing in finite fields over the canonical basis. It consists of two parts: a normal power-sum part and modular-re- duction 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 AND gates and XOR gates to reach low time complexity of . As compared to the conventional cellular-array structures for in , 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 corre- sponding reduced structures based on three special-form generating poly- nomials, including the trinomial , 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/di- visions and exponentiations in , is also constructed based on the proposed power-sum circuit.