论文部分内容阅读
随着互联网的发展和各种电子产品的普及,人们对信息安全提出了更高的要求。公钥密码体制作为安全性较高的一种密码体制应用愈加广泛,模幂运算作为公钥密码体制的核心部分直接影响着公钥密码体制的执行速度。然而计算机执行大数模幂运算速度慢这一问题,虽然在各种研究与算法不断提出的历史与现状下有所缓解,但并没有从根本上得到解决,这也使得公钥密码体制的更广泛应用遇到了瓶颈。本文主要内容如下:(1)对目前具有代表性的大数模幂计算方法进行了总结与分析,包括进行大数模幂运算的经典算法、针对特定情况或利用特殊性质的特殊方法、具有理论指导意义的理论方法以及求乘积和余数的底层实现;(2)针对目前缺乏滑动窗口法复杂度深入研究的问题,利用马尔可夫状态转移矩阵对滑动窗口法的效率进行分析,给出了二进制编码下的复杂度精确表达式,实验表明理论值与实际值在各情况下误差绝对值不超过0.05次模乘,该分析法可以应用于任何确定状态转移概率的编码;(3)提出了一种基于加法序列思想的滑动窗口法预计算部分改进方法,给出了具有实际应用性的算法来求通过多个给定值的加法序列,实验表明这种方法可以很好的改进当窗口长度选择过大时的预计算利用率从而达到提升总体效率的目的;(4)结合幂树法提出了一种完全幂树的概念,分析了这种幂树的性质,并将二进制法、分块法、滑动窗口法等大数模幂计算方法与完全幂树中的路径进行对映;提出了一种带参搜索法,这种方法通过利用给定参数进行搜索得到最优方案,根据方案进行模幂计算,该方法还可结合其他大数模幂算法进行计算,实验表明该方法在一定程度上提高了模幂计算的效率。