Paper 2014/972
A Chinese Remainder Theorem Approach to BitParallel GF(2^n) Polynomial Basis Multipliers for Irreducible Trinomials
Haining Fan
Abstract
We show that the step “modulo the degreen 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 bitparallel GF(2^n) multipliers for irreducible trinomials u^n + u^k + 1 on GF(2) where 1 < k ≤ n=2. For some values of n, our architectures have the same time complexity as the fastest bitparallel 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 ≤ n=2, the proposed multipliers beat the current fastest parallel multipliers for 290 values of n when (n − 1)=3 ≤ k ≤ n=2: they have the same time complexity, but the space complexities are reduced by 8.4% on average.
Note: I corrected a few typos.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 implementation
 Contact author(s)
 fhn @ tsinghua edu cn
 History
 20150423: last of 3 revisions
 20141128: received
 See all versions
 Short URL
 https://ia.cr/2014/972
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/972, author = {Haining Fan}, title = {A Chinese Remainder Theorem Approach to BitParallel GF(2^n) Polynomial Basis Multipliers for Irreducible Trinomials}, howpublished = {Cryptology ePrint Archive, Paper 2014/972}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/972}}, url = {https://eprint.iacr.org/2014/972} }