A new architecture for a parallel finite field multiplier with low complexity based on composite fields

Author

Paar, Christof

Author_Institution

Dept. of Electr. & Comput. Eng., Worcester Polytech. Inst., MA

Volume

45

Issue

7

fYear

1996

fDate

7/1/1996 12:00:00 AM

Firstpage

856

Lastpage

861

Abstract

A bit parallel structure for a multiplier with low complexity in Galois fields is introduced. The multiplier operates over composite fields GF((2ⁿ)^m), with k=nm. The Karatsuba-Ofman algorithm (A. Karatsuba and Y. Ofmanis, 1963) is investigated and applied to the multiplication of polynomials over GF(2ⁿ). It is shown that this operation has a complexity of order O(k^log23) under certain constraints regarding k. A complete set of primitive field polynomials for composite fields is provided which perform module reduction with low complexity. As a result, multipliers for fields GF(2^k) up to k=32 with low gate counts and low delays are listed. The architectures are highly modular and thus well suited for VLSI implementation

Keywords

Galois fields; computational complexity; parallel algorithms; parallel architectures; polynomials; Galois fields; VLSI implementation; bit parallel structure; composite fields; gate counts; low complexity; module reduction; parallel finite field multiplier; polynomial multiplication; primitive field polynomials; Cryptography; Delay; Digital communication; Error correction codes; Galois fields; Graphics; Hardware; Information theory; Polynomials; Very large scale integration;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.508323

Filename

508323