Finite fields have been used for numerous applications including error-control coding and cryptography. The design of efficient multipliers, dividers, and exponentiators for finite field arithmetic is of great practical concern. In this paper, we explore and classify algorithms for finite field multiplication, squaring, and exponentiation into least significant bit first (LSB-first) scheme and most significant bit first (MSB-first) scheme, and implement these algorithms using semisystolic arrays. For finite field multiplication (for programmable as well as fixed field order) and exponentiation, we conclude that LSB-first algorithms are more efficient as their basic cells have less critical path computation time. Another advantage of LSB-first scheme is its capability of achieving substructure sharing among multiple operations, which could lead to savings in hardware when these arithmetic units are used as building blocks for a large system. For finite field squaring operation, it turns out that the MSB-first algorithm is more efficient as it leads to simpler architectures. Bit-level pipelined semisystolic architectures utilize broadcast signals. As a result, these require much less number of latches and lead to much smaller latency than the corresponding systolic array, with the same cycle time (the computation time in one basic cell). Efficient VLSI implementation of semisystolic multipliers, squarers and exponentiators are designed and compared with existing architectures. A novel architecture for computing ABn + C using power representation is also presented.
|Original language||English (US)|
|Number of pages||13|
|Journal||IEEE Transactions on Very Large Scale Integration (VLSI) Systems|
|State||Published - 1998|
Bibliographical noteFunding Information:
Manuscript received April 25, 1995; revised August 25, 1997. This work was supported in part by the Advanced Research Project Agency and the Solid State Electronics Directorate, Wright-Patterson AFB, under Contract AF/F33615-93-C-1309, and by the Army Research Office under Grant DA/DAAH-94-G-0405.
- Finite field
- Polynomial basis
- Power basis