Efficient finite field serial/parallel multiplication

Abstract

Finite field has received a lot of attention due to its widespread applications in cryptography, coding theory, etc. Design of efficient finite field arithmetic architectures is very important and of great practical concern. In this paper, a new bit-serial/parallel finite field multiplier is presented with standard basis representation. This design is regular and well suited for VLSI implementation. As compared to existing serial/parallel finite field multipliers, it has smaller critical path, lower latency and can be easily pipelined. When it is used as a building block for large systems, it can achieve more savings in hardware in the broadcast structures by utilizing sub-structure sharing technique. This paper also presents two generalized algorithms for finite field serial/parallel multiplication. They can be used to derive efficient bit-parallel, digit-serial or bit-serial multiplication architectures. The optimal primitive polynomials over GF(2/sup m/) (for 2/spl les/m/spl les/9) are provided which will generate structures with minimum hardware complexity and relatively more flexibilities for feasible digit-sizes with respect to the proposed algorithms. Finally a multiplier over GF(2/sup 8/) is given as an example showing how to derive finite field multipliers using the proposed algorithms. This multiplier has less number of transistors, smaller critical path and consumes less power compared to the existing semi-systolic architecture.