-
题名模幂滑动窗口法分析及加法链在预计算中的应用
- 1
-
-
作者
屈晓
孙达志
-
机构
天津大学计算机科学与技术学院
中国科学院信息工程研究所
-
出处
《计算机工程》
CAS
CSCD
2014年第7期263-266,共4页
-
基金
国家自然科学基金资助项目"公钥密码体制中多维模幂计算方法及其应用研究"(61003306)
-
文摘
滑动窗口法是计算大数模幂问题应用最广泛的方法之一,然而针对此方法复杂度的精确理论分析却十分稀少。在计算效率方面,当窗口选择过大时,预计算量呈指数型增长。针对这2个问题,利用马尔可夫状态转移矩阵对滑动窗口法进行效率分析,给出大数模幂计算在二进制编码下滑动窗口法的精确复杂度表示,其理论值与实际值在各情况下误差绝对值不超过0.1次模乘。同时提出一种利用加法链进行预计算的思想,给出一种计算机执行简单可行的求加法序列的算法,用于求解由多个给定值构成的加法链。实验结果证明,该算法能够提高窗口选择过大时的计算效率,并可用于同一信息的多方发送等。
-
关键词
模幂
滑动窗口法
马尔可夫状态转移矩阵
精确复杂度
预计算
加法链
大窗口
-
Keywords
exponentiation
sliding window method
Markov state transfer matrix
exact complexity
precomputation
addition chain
big window
-
分类号
TP309.2
[自动化与计算机技术—计算机系统结构]
-