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

摘要

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