北京邮电大学学报

  • EI核心期刊

北京邮电大学学报 ›› 2011, Vol. 34 ›› Issue (6): 47-50.doi: 10.13190/jbupt.201106.47.lizhh

• 论文 • 上一篇    下一篇

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

李智慧1,崔毅东2,徐惠民3,金跃辉4   

  1. 1. 北京邮电大学
    2. 北京邮电大学信息与通讯工程学院;北京邮电大学网络与交换技术国家重点实验室
    3. 北京邮电大学 电信工程学院
    4. 北京邮电大学网络与交换技术国家重点实验室
  • 收稿日期:2011-01-19 修回日期:2011-08-27 出版日期:2011-12-28 发布日期:2011-10-18
  • 通讯作者: 李智慧 E-mail:lizhihui8601@gmail.com
  • 作者简介:李智慧(1981-),男,博士生,E-mail:lizhihui8601@gmail.com 徐惠民(1941-),男,教授,博士生导师
  • 基金资助:
    国家重点基础研究发展计划项目;国家高技术研究发展计划项目;国家自然科学基金项目

Improved algorithm for Computation of Chebyshev polynomial over finite field

  • Received:2011-01-19 Revised:2011-08-27 Online:2011-12-28 Published:2011-10-18
  • Contact: Zhi-Hui LI E-mail:lizhihui8601@gmail.com

摘要:

对计算有限域上切比雪夫多项式的特征多项式算法进行改进以提高算法的执行速度。首先在该算法中用蒙哥马利模乘代替普通模乘运算,避免了取模运算中的除法操作,从而降低单次模乘运算的平均运行时间;其次对蒙哥马利模平方运算的算法流程进行优化,减少其中单精度乘法的执行次数。仿真结果表明改进后的特征多项式算法其运行速度有了很大提高。

Abstract:

A Characteristic polynomial algorithm 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 to reduce the average time cost on a multiplication, by avoiding the division operation in modular arithmetic. Second, the procedure of Montgomery modular square algorithm is modified to reduce the required number of single-precision multiplications. The simulation results show that the modified algorithm is faster than the original one.

中图分类号: