Efficient semisystolic architectures for finite-field arithmetic

Surendra K. Jain, Leilei Song, Keshab K Parhi

Research output: Contribution to journalArticle

110 Citations (Scopus)

Abstract

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 languageEnglish (US)
Pages (from-to)101-113
Number of pages13
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume6
Issue number1
DOIs
StatePublished - Dec 1 1998

Fingerprint

Systolic arrays
Cryptography
Hardware

Keywords

  • Cellular-array
  • Exponentiator
  • Finite field
  • LSB-first
  • MSB-first
  • Multiplier
  • Polynomial basis
  • Power basis
  • Semisystolic
  • Squarer

Cite this

Efficient semisystolic architectures for finite-field arithmetic. / Jain, Surendra K.; Song, Leilei; Parhi, Keshab K.

In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 6, No. 1, 01.12.1998, p. 101-113.

Research output: Contribution to journalArticle

@article{887c58a73f224529937e97e229868ef8,
title = "Efficient semisystolic architectures for finite-field arithmetic",
abstract = "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.",
keywords = "Cellular-array, Exponentiator, Finite field, LSB-first, MSB-first, Multiplier, Polynomial basis, Power basis, Semisystolic, Squarer",
author = "Jain, {Surendra K.} and Leilei Song and Parhi, {Keshab K}",
year = "1998",
month = "12",
day = "1",
doi = "10.1109/92.661252",
language = "English (US)",
volume = "6",
pages = "101--113",
journal = "IEEE Transactions on Very Large Scale Integration (VLSI) Systems",
issn = "1063-8210",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "1",

}

TY - JOUR

T1 - Efficient semisystolic architectures for finite-field arithmetic

AU - Jain, Surendra K.

AU - Song, Leilei

AU - Parhi, Keshab K

PY - 1998/12/1

Y1 - 1998/12/1

N2 - 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.

AB - 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.

KW - Cellular-array

KW - Exponentiator

KW - Finite field

KW - LSB-first

KW - MSB-first

KW - Multiplier

KW - Polynomial basis

KW - Power basis

KW - Semisystolic

KW - Squarer

UR - http://www.scopus.com/inward/record.url?scp=0032023744&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032023744&partnerID=8YFLogxK

U2 - 10.1109/92.661252

DO - 10.1109/92.661252

M3 - Article

VL - 6

SP - 101

EP - 113

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

SN - 1063-8210

IS - 1

ER -