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

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

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

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.