p元扩域上的快速乘法

基于剩余算术理论构造了一类F_px]上的项式PAPB,给出了该型不可约多项式的存在数量估计;然后,利用剩余算术和中国剩余定理,提出了一种模PAPB乘法的快速实现算法;最后给出结果分析.理论和实验结果表明,在一定条件下,给出算法的计算复杂度仅有O(k~(1.5)),优于常用模二项式乘法O(k~2)的计算复杂度.因此,该类多项式在最优扩域和椭圆曲线算法中有较好的应用前景.

Efficient multiplication for finite fields of p characteristic

Based on residue arithmetic, a new form of polynomial named PAPB in F_px] had been constructed. The amount and distribution of such irreducible polynomials had also been investigated. Then, an efficient algorithm for multiplication modulo PAPB had been proposed using residue arithmetic and Chinese remainder theorem. In the end, the result analysis was given. The theoretic analysis and simulation experiment show that for some finite field of medium prime characteristic, the given algorithm only costs O(k~(1.5)) operations in F_p while the multiplication modulo irreducible binomial cost O(k~2) operations, which shows a better performance. As a result, the work presents an interesting perspective for optimal extension field and elliptic curve cryptography.