文档介绍：天津大学
硕 士 学 位 论 文
基于公钥密码体制的模幂算法执行效率研究
专业名称： 计算机科学与技术
作者姓名： 屈晓
指导老师： 孙达志
基于公钥密码体制的模幂算法执行效率
研究
Analysis of Modular Exponentiation
Algorithms Based on Public-key
Cryptosystem
学科专业：计算机科学与技术
研 究 生：屈晓
指导教师：孙达志 副教授
天津大学计算机科学与技术学院
二零一三年十一月
独创性声明
本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的
研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表
或撰写过的研究成果，也不包含为获得 天津大学 或其他教育机构的学位或证
书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中
作了明确的说明并表示了谢意。
学位论文作者签名： 签字日期： 年 月 日
学位论文版权使用授权书
本学位论文作者完全了解 天津大学 有关保留、使用学位论文的规定。
特授权 天津大学 可以将学位论文的全部或部分内容编入有关数据库进行检
索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校
向国家有关部门或机构送交论文的复印件和磁盘。
（保密的学位论文在解密后适用本授权说明）
学位论文作者签名： 导师签名：
签字日期： 年 月 日 签字日期： 年 月 日
摘 要
随着互联网的发展和各种电子产品的普及，人们对信息安全提出了更高的要
求。公钥密码体制作为安全性较高的一种密码体制应用愈加广泛，模幂运算作为
公钥密码体制的核心部分直接影响着公钥密码体制的执行速度。然而计算机执行
大数模幂运算速度慢这一问题，虽然在各种研究与算法不断提出的历史与现状下
有所缓解，但并没有从根本上得到解决，这也使得公钥密码体制的更广泛应用遇
到了瓶颈。
本文主要内容如下：
(1) 对目前具有代表性的大数模幂计算方法进行了总结与分析，包括进行大
数模幂运算的经典算法、针对特定情况或利用特殊性质的特殊方法、具有理论指
导意义的理论方法以及求乘积和余数的底层实现；
(2) 针对目前缺乏滑动窗口法复杂度深入研究的问题，利用马尔可夫状态转
移矩阵对滑动窗口法的效率进行分析，给出了二进制编码下的复杂度精确表达
式，实验表明理论值与实际值在各情况下误差绝对值不超过 次模乘，该分
析法可以应用于任何确定状态转移概率的编码；
(3) 提出了一种基于加法序列思想的滑动窗口法预计算部分改进方法，给出
了具有实际应用性的算法来求通过多个给定值的加法序列，实验表明这种方法可
以很好的改进当窗口长度选择过大时的预计算利用率从而达到提升总体效率的
目的；
(4) 结合幂树法提出了一种完全幂树的概念，分析了这种幂树的