p元扩域上的快速乘法
Efficient multiplication for finite fields of p characteristic作者机构:上海交通大学信息安全工程学院上海200240 上海交通大学电信学院上海200240
出 版 物:《通信学报》 (Journal on Communications)
年 卷 期:2009年第30卷第11期
页 面:101-105,112页
核心收录:
学科分类:0810[工学-信息与通信工程] 1205[管理学-图书情报与档案管理] 0839[工学-网络空间安全] 08[工学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术(可授工学、理学学位)] 081202[工学-计算机软件与理论]
摘 要:基于剩余算术理论构造了一类Fp[x]上的多项式PAPB,给出了该型不可约多项式的存在数量估计;然后,利用剩余算术和中国剩余定理,提出了一种模PAPB乘法的快速实现算法;最后给出结果分析。理论和实验结果表明,在一定条件下,给出算法的计算复杂度仅有O(k1.5),优于常用模二项式乘法O(k2)的计算复杂度。因此,该类多项式在最优扩域和椭圆曲线算法中有较好的应用前景。