Cryptology ePrint Archive: Report 2014/972

A Chinese Remainder Theorem Approach to Bit-Parallel GF(2^n) Polynomial Basis Multipliers for Irreducible Trinomials

Haining Fan

Abstract: We show that the step “modulo the degree-n field generating irreducible polynomial” in the classical definition of the GF(2^n) multiplication operation can be avoided. This leads to an alternative representation of the finite field multiplication operation. Combining this representation and the Chinese Remainder Theorem, we design bit-parallel GF(2^n) multipliers for irreducible trinomials u^n + u^k + 1 on GF(2) where 1 < k &#8804; n=2. For some values of n, our architectures have the same time complexity as the fastest bit-parallel multipliers – the quadratic multipliers, but their space complexities are reduced. Take the special irreducible trinomial u^(2k) + u^k + 1 for example, the space complexity of the proposed design is reduced by about 1=8, while the time complexity matches the best result. Our experimental results show that among the 539 values of n such that 4 < n < 1000 and x^n+x^k+1 is irreducible over GF(2) for some k in the range 1 < k &#8804; n=2, the proposed multipliers beat the current fastest parallel multipliers for 290 values of n when (n &#8722; 1)=3 &#8804; k &#8804; n=2: they have the same time complexity, but the space complexities are reduced by 8.4% on average.

Category / Keywords: implementation

Date: received 27 Nov 2014, last revised 22 Apr 2015

Contact author: fhn at tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Note: I corrected a few typos.

Version: 20150423:015443 (All versions of this report)

Short URL: ia.cr/2014/972

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]