论文部分内容阅读
基于剩余算术理论构造了一类Fp[x]上的多项式PAPB,给出了该型不可约多项式的存在数量估计;然后,利用剩余算术和中国剩余定理,提出了一种模PAPB乘法的快速实现算法;最后给出结果分析。理论和实验结果表明,在一定条件下,给出算法的计算复杂度仅有O(k1.5),优于常用模二项式乘法O(k2)的计算复杂度。因此,该类多项式在最优扩域和椭圆曲线算法中有较好的应用前景。
Based on the residual arithmetic theory, a class of polynomials PAPB on Fp [x] is constructed, and the number of existence of this type of irreducible polynomial is given. Then, a fast implementation of modulo PAPB multiplication is proposed by using residual arithmetic and Chinese residual theorem Algorithm; finally give the result analysis. The theoretical and experimental results show that under certain conditions, the computational complexity of the proposed algorithm is only O (k1.5), which is superior to the computational complexity of the common mode binomial multiplication O (k2). Therefore, the polynomial of this kind has good application prospects in the optimal expansion and elliptic curve algorithm.