计算机工程

• 开发研究与工程应用 • 上一篇    下一篇

模幂滑动窗口法分析及加法链在预计算中的应用

屈 晓1,孙达志1,2   

  1. (1. 天津大学计算机科学与技术学院,天津 300072;2. 中国科学院信息工程研究所,北京 100093)
  • 收稿日期:2013-05-13 出版日期:2014-07-15 发布日期:2014-07-14
  • 作者简介:屈 晓(1986-),男,硕士研究生,主研方向:信息与网络安全,应用密码学;孙达志,副教授、博士。
  • 基金项目:
    国家自然科学基金资助项目“公钥密码体制中多维模幂计算方法及其应用研究”(61003306)。

Analysis of Exponentiation Sliding Window Method and Application of Addition Chain in Precomputation

QU Xiao 1, SUN Da-zhi 1,2   

  1. (1. School of Computer Science and Technology, Tianjin University, Tianjin 300072, China; 2. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China)
  • Received:2013-05-13 Online:2014-07-15 Published:2014-07-14

摘要: 滑动窗口法是计算大数模幂问题应用最广泛的方法之一,然而针对此方法复杂度的精确理论分析却十分稀少。在计算效率方面,当窗口选择过大时,预计算量呈指数型增长。针对这2个问题,利用马尔可夫状态转移矩阵对滑动窗口法进行效率分析,给出大数模幂计算在二进制编码下滑动窗口法的精确复杂度表示,其理论值与实际值在各情况下误差绝对值不超过0.1次模乘。同时提出一种利用加法链进行预计算的思想,给出一种计算机执行简单可行的求加法序列的算法,用于求解由多个给定值构成的加法链。实验结果证明,该算法能够提高窗口选择过大时的计算效率,并可用于同一信息的多方发送等。

关键词: 模幂, 滑动窗口法, 马尔可夫状态转移矩阵, 精确复杂度, 预计算, 加法链, 大窗口

Abstract: Sliding window method is one of the most widely used methods for exponentiation, but analysis on its exact computational complexity are few. And when the window size becomes bigger, the total of precomputations grows exponentially. An analysis of the exact complexity of sliding window method with Markov transfer matrix is presented. It presents an expression of the exact complexity in binary code. The difference between theoretical and experimental values is less than 0.1 time of modular multiplication. After that, a method with addition chain passing all given values in precomputation is proposed. It generates an algorithm which is computationally feasible for computer implementation. Experimental result shows that this method improves the efficiency greatly when the window size is big. This thought can also be used in the case of one message sending to many clients.

Key words: exponentiation, sliding window method, Markov state transfer matrix, exact complexity, precomputation, addition chain, big window

中图分类号: