Paper 2015/498
Low Space Complexity CRTbased BitParallel 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 CRTbased 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^21 XOR gates. Our experimental results show that among the 539 values of n∈[5,999] such that f is irreducible for some k∈[2,n2], 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 CRTbased 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 CRTbased multipliers consider the case k∈[2,n/2], and the improvement rate is only 8.4% on average.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 Finite fieldmultiplicationpolynomial basisthe Chinese Remainder Theoremirreducible polynomial
 Contact author(s)
 zjjzhaoyun @ 126 com
 History
 20150605: revised
 20150526: received
 See all versions
 Short URL
 https://ia.cr/2015/498
 License

CC BY
BibTeX
@misc{cryptoeprint:2015/498, author = {Jiajun Zhang and Haining Fan}, title = {Low Space Complexity CRTbased BitParallel GF(2^n) Polynomial Basis Multipliers for Irreducible Trinomials}, howpublished = {Cryptology ePrint Archive, Paper 2015/498}, year = {2015}, note = {\url{https://eprint.iacr.org/2015/498}}, url = {https://eprint.iacr.org/2015/498} }