**Low Space Complexity CRT-based Bit-Parallel GF(2^n) Polynomial Basis Multipliers for Irreducible Trinomials**

*Jiajun Zhang and Haining Fan*

**Abstract: **By selecting the largest possible value of k∈(n/2,2n/3], we further reduce the AND and XOR gate complexities of the CRT-based hybrid parallel GF(2^n) polynomial basis multipliers for the irreducible trinomial f = u^n + u^k + 1 over GF(2): they are always less than those of the current fastest parallel multipliers – quadratic multipliers, i.e., n^2 AND gates and n^2-1 XOR gates. Our experimental results show that among the 539 values of n∈[5,999] such that f is irreducible for some k∈[2,n-2], there are 317 values of n such that k∈(n/2,2n/3]. For these irreducible trinomials, the AND and XOR gate complexities of the CRT-based hybrid multipliers are reduced by 15.3% on average. Especially, for the 124 values of such n, the two kinds of multipliers have the same time complexity, but the space complexities are reduced by 15.5% on average. As a comparison, the previous CRT-based multipliers consider the case k∈[2,n/2], and the improvement rate is only 8.4% on average.

**Category / Keywords: **Finite field, multiplication, polynomial basis, the Chinese Remainder Theorem,irreducible polynomial

**Date: **received 26 May 2015, last revised 4 Jun 2015

**Contact author: **zjjzhaoyun at 126 com

**Available format(s): **PDF | BibTeX Citation

**Version: **20150605:031609 (All versions of this report)

**Short URL: **ia.cr/2015/498

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]