A Matrix Decomposition Method for Optimal Normal Basis Multiplication

Can Kızılkale; Ömer Eǧecioǧlu; Çetin Kaya Koç

Paper 2015/742

A Matrix Decomposition Method for Optimal Normal Basis Multiplication

Can Kızılkale, Ömer Eǧecioǧlu, and Çetin Kaya Koç

Abstract

We introduce a matrix decomposition method and prove that multiplication in GF(2^k) with a Type 1 optimal normal basis for can be performed using k^2-1 XOR gates irrespective of the choice of the irreducible polynomial generating the field. The previous results achieved this bound only with special irreducible polynomials. Furthermore, the decomposition method performs the multiplication operation using 1.5k(k-1) XOR gates for Type 2a and 2b optimal normal bases, which matches previous bounds.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: Finite fields
Contact author(s): koc @ cs ucsb edu
History: 2015-07-24: revised; 2015-07-24: received; See all versions
Short URL: https://ia.cr/2015/742
License: CC BY

BibTeX

@misc{cryptoeprint:2015/742,
      author = {Can Kızılkale and Ömer Eǧecioǧlu and Çetin Kaya Koç},
      title = {A Matrix Decomposition Method for Optimal Normal Basis Multiplication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/742},
      year = {2015},
      url = {https://eprint.iacr.org/2015/742}
}