Relationship between GF(2^m) Montgomery and Shifted Polynomial Basis Multiplication Algorithms

Author

Fan, Haining ; Hasan, M. Anwar

Author_Institution

Dept. of Electr. & Comput. Eng., Waterloo Univ., Ont.

Volume

55

Issue

9

fYear

2006

Firstpage

1202

Lastpage

1206

Abstract

Applying the matrix-vector product idea of the Mastrovito multiplier to the GF(2^m) Montgomery multiplication algorithm, we present a new parallel multiplier for irreducible trinomials. This multiplier and the corresponding shifted polynomial basis (SPB) multiplier have the same circuit structure for the same set of parameters. Furthermore, by establishing isomorphisms between the Montgomery and the SPB constructions of GF(2^m), we show that the Montgomery algorithm can be used to perform the SPB multiplication without any changes and vice versa

Keywords

Galois fields; matrix multiplication; multiplying circuits; parallel algorithms; polynomials; GF(2^m) Montgomery multiplication algorithm; Mastrovito multiplier; irreducible trinomials; matrix-vector product; parallel multiplier; shifted polynomial basis; Algorithm design and analysis; Circuits; Cryptography; Galois fields; Hardware; Polynomials; Very large scale integration; Finite field; Montgomery multiplication algorithm; irreducible trinomial.; multiplication; polynomial basis; shifted polynomial basis;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/TC.2006.152

Filename

1668047