A Chinese Remainder Theorem Approach to Bit-Parallel $GF(2^{n})$ Polynomial Basis Multipliers for Irreducible Trinomials
A Chinese Remainder Theorem Approach to Bit-Parallel $GF(2^{n})$ Polynomial Basis Multipliers for Irreducible Trinomials
复制标题
DOI：
10.1109/tc.2015.2428704
复制
发表时间：
2016-02
影响因子：
3.7
通讯作者：
H. Fan
中科院分区：
文献类型：
--
作者：
H. Fan
我们证明了在经典的GF（2n）乘法运算定义中的“模n次域生成不可约多项式”的步骤是可以避免的。这导致有限域乘法运算的另一种表示。结合这一表示和中国剩余定理，我们设计了GF（2）上不可约三项式un + uk + 1的位并行GF（2n）乘法器，其中1 <; k ≤ n/2.对于某些值的n，我们的架构具有相同的时间复杂度的最快的位并行乘法器的二次乘法器，但它们的空间复杂度降低。以特殊的不可约三项式u2 k + uk + 1为例，所提出的设计的空间复杂度降低了约1/8，而时间复杂度则与最佳结果相匹配。我们的实验结果表明，在539个n值中，4 <; n <; 1，000且xn + xk + 1在GF（2）上不可约，其中k在1 <; k ≤ n=2的范围内，当（n - 1）/3 ≤ k ≤ n/2时，所提出的乘法器在290个n值中击败了当前最快的并行乘法器：它们具有相同的时间复杂度，但空间复杂度平均降低了8：4%。
We show that the step “modulo the degree-n field generating irreducible polynomial” in the classical definition of the GF (2n) 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 (2n) multipliers for irreducible trinomials un + uk + 1 on GF (2) where 1 <; k ≤ 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 u2k + uk + 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 <; 1,000 and xn + xk + 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 percent on average.