有限域切比雪夫多项式的改进算法  

Improved Algorithm for Computation of Chebyshev Polynomial over Finite Field

作　　者：李智慧[1,2] 崔毅东[1,3] 金跃辉[1] 徐惠民[2] 

机构地区：[1]北京邮电大学网络与交换技术国家重点实验室,北京100876 [2]北京邮电大学信息与通信工程学院,北京100876 [3]北京邮电大学软件学院,北京100876

出　　处：《北京邮电大学学报》2011年第6期47-50,77,共5页Journal of Beijing University of Posts and Telecommunications

基　　金：国家重点基础研究发展计划项目(2009CB320505);国家高技术研究发展计划项目(2010AA012501);国家自然科学基金项目(61002011;90924029)

摘　　要：对计算有限域上切比雪夫多项式的特征多项式算法(CPA)进行了改进,以提高算法的执行速度.首先用蒙哥马利模乘代替原有算法中的普通模乘运算,从而降低单次模乘运算的平均运行时间;其次对蒙哥马利模平方运算的算法流程进行了优化,减少其中单精度乘法的执行次数.仿真结果表明,改进后的CPA其运行速度有了很大提高.A characteristic polynomial algorithm （CPA） for computation of Chebyshev polynomial over finite field is modified to achieve faster execution speed. First, the Montgomery modular multiplication is introduced to replace the classical modular multiplication, and reduce the average time cost of one multi- plication. Second, the procedure of Montgomery modular square algorithm is optimized to reduce the required number of single-precision multiplications. Simulations show that the modified algorithm is faster than the original one.

关 键 词：切比雪夫多项式 特征多项式算法 蒙哥马利模乘 蒙哥马利模平方 

分 类 号：TP309.07[自动化与计算机技术—计算机系统结构]