Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (36): 48-50.DOI: 10.3778/j.issn.1002-8331.2010.36.013

• 研究、探讨 • Previous Articles     Next Articles

Consistency analysis of addition chains for several fast algorithms of modular exponentiation

DONG Fu-guo,LI Yu-rong   

  1. School of Computer Science and Technology,Shandong Institute of Business and Technology,Yantai,Shandong 264005,China
  • Received:2010-07-21 Revised:2010-09-06 Online:2010-12-21 Published:2010-12-21
  • Contact: DONG Fu-guo

几种方幂模快速算法的加法链一致性分析

董付国,厉玉蓉   

  1. 山东工商学院 计算机科学与技术学院,山东 烟台 264005
  • 通讯作者: 董付国

Abstract: Modular exponentiation is the most frequently used and time-cost part in RSA,whose fast algorithm is one of the focuses of RSA study,and to speed up the computation of modular exponentiation is most important to the performance and wide use of RSA.This paper studies Qin Jiu-shao algorithm,blocking algorithm,addition chains algorithm,and adaptive binary partition table searching method.Another contribution of this paper is that the above algorithms are analyzed from the point of view of addition chains.In the point of view of addition chains,they are accordant,and adaptive binary partition table searching method can get higher efficiency than Qin Jiu-shao algorithm and blocking algorithm,but may be further improved.

Key words: modular exponentiation, Qin Jiu-shao algorithm, blocking algorithm, adaptive binary partition table searching method, addition chains

摘要: 在RSA算法中,最主要、使用最频繁同时也是最耗时的是方幂模运算。自从RSA算法提出后,方幂模快速算法一直是研究重点之一,方幂模算法的改进和速度的提高直接影响RSA算法的整体性能和广泛应用。深入分析了方幂模计算的秦九韶算法、分块算法、二进制自适应分组查表法和最短加法链算法,提出了加法链的统一思想,认为这几种算法在本质上都是加法链算法,为以后的研究工作指出了方向。同时指出二进制自适应分组查表法可以获得更高的整体效率,但仍有进一步提升的空间。

关键词: 方幂模, 秦九韶算法, 分块算法, 二进制自适应分组查表法, 加法链

CLC Number: