Cryptology ePrint Archive: Report 2004/137

New GF(2n) Parallel Multiplier Using Redundant Representation

Haining Fan and Yiqi Dai

Abstract: A new GF(2n) redundant representation is presented. Squaring in the representation is almost cost-free. Based on the representation, two multipliers are proposed. The XOR gate complexity of the first multiplier is lower than a recently proposed normal basis multiplier when CN (the complexity of the basis) is larger than 3n-1.

Category / Keywords: Finite field, normal basis, redundant set, Massey-Omura multiplier.

Publication Info: This paper is published in: H. Fan, Researches in GF(2n) Multiplication Algorithms, PhD dissertation, Tsinghua University, 2004. (in Chinese)

Date: received 7 Jun 2004, last revised 5 Aug 2006

Contact author: fan_haining at yahoo com

Available format(s): PDF | BibTeX Citation

Version: 20060806:020208 (All versions of this report)

Short URL: ia.cr/2004/137

Discussion forum: Show discussion | Start new discussion