Cryptology ePrint Archive: Report 2015/742

A Matrix Decomposition Method for Optimal Normal Basis Multiplication

Can Kızılkale and Ö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.

Category / Keywords: Finite fields

Date: received 23 Jul 2015, last revised 24 Jul 2015

Contact author: koc at cs ucsb edu

Available format(s): PDF | BibTeX Citation

Version: 20150724:154305 (All versions of this report)

Short URL: ia.cr/2015/742

Discussion forum: Show discussion | Start new discussion