最佳滑动窗口编码法及其在快速模幂乘中的应用

Optimal Sliding Window Coding Method and Its Application in Fast Modular Power Multiplication

大数模幂乘是实现RSA、E1Gamal、DSA等公钥算法的基本运算,其运算速度对这些算法的实现起着重要的作用.首先对基于滑动窗口的模乘算法作了部分改进大大减少了空间复杂度;给出了最佳窗口长度的计算方法.然后将改进后的算法推广到模幂运算.通过分析得知,当RSA的加密指数e的长度为512位时,该算法平均只需要做616次大数模乘便可实现A×BemodN运算.最后用滑动窗口法与二进制法、加法链法、Yacobi法等其他模幂乘算法进行了比较,并指出滑动窗口法和Yacobi法是目前最好的模幂乘算法.

Modular power and modular multiplication are the basic algorithms for implementing the public key algorithms such as RSA, ElgGamal and DSA etc. whose speed is the key and decided by the above. Firstly, the paper improved the sliding window algorithm for modular multiplication by largely reducing the space complexity and provided the algorithm for computing the length of optimum window. Secondly the paper generalized the method to fast modular power. Through analysis, this algorithm needs only 616 times large integer number multiplication to compute A×Be mod N, if the length of the encryption exponent of RSA is 512 bits. Lastly, the paper compared the sliding window algorithm with other algorithm such as Binary Method, Addition Chain Method and Yacobi Method etc. and pointed out that sliding window method and Yacobi Method are the best modular power multiplication at present.