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

摘要：

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

关键词：模幂、滑动窗口法、马尔可夫状态转移矩阵、精确复杂度、预计算、加法链、大窗口

分类号：TP309.2(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目“公钥密码体制中多维模幂计算方法及其应用研究”61003306。

在线出版日期：2014-08-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：263-266