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

• 作者: 孙达志 屈晓
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 模幂 滑动窗口法 马尔可夫状态转移矩阵 精确复杂度 预计算 加法链 大窗口
• 年，卷（期）: 2014,（7）
• 所属期刊栏目: 开发研究与工程应用
• 页码范围: 263-266
• 页数: 4页
• 分类号: TP309.2
• 字数: 4170字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2014.07.054

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙达志	天津大学计算机科学与技术学院	6	29	4.0	5.0
5	屈晓	天津大学计算机科学与技术学院	1	0	0.0	0.0