计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (4): 80-82.

• 学术探讨 • 上一篇    下一篇

一种定点快速标量乘算法的优化

殷新春,侯红祥   

  1. 扬州大学 计算机科学与工程系,江苏 扬州 225009
  • 收稿日期:2007-06-25 修回日期:2007-08-31 出版日期:2008-02-01 发布日期:2008-02-01
  • 通讯作者: 殷新春

Optimization of fast fixed point fast scalar multiplication algorithm

YIN Xin-chun,HOU Hong-xiang   

  1. Department of Computer Science and Engineering,Yangzhou University,Yangzhou,Jiangsu 225009,China
  • Received:2007-06-25 Revised:2007-08-31 Online:2008-02-01 Published:2008-02-01
  • Contact: YIN Xin-chun

摘要: 标量乘法是实现椭圆曲线密码体制的瓶颈问题,利用NAF编码、预计算表法和Yen-Laih法分别在三个阶段对Lim-Lee算法进行优化,新的定点标量乘算法在赋值阶段动态扫描矩阵宽度为w的非全零列窗口,结合2kP底层域快速算法和扩充过的预计算表来提高计算效率。当位长是160时,新算法效率比Lim-Lee算法提高22.7%,192时提高23%,224时提高23.3%。

关键词: ECC, 定点标量乘法, NAF编码, 预计算表法, Yen-Laih法

Abstract: Scalar multiplication is the bottleneck of ECC.This paper optimizes the Lim-Lee algorithm with NAF method,pre-compute table and Yen-Laih method in three stages separately.The new fixed-point scalar multiplication algorithm dynamicly scans the matrix to get nonzero windows with length limited in w in the evaluation stage,and integrates with 2kP field fast algorithm and extended pre-compute table to improve compute efficiency.When digit length is 160,the efficiency of new algorithm improves about 22.7% than Lim-Lee algorithm,about 23% when 192 and 23.3% when 224.

Key words: EEC, fixed-point scalar multiplication, NAF method, pre-compute table, Yen-Laih method