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

《模幂滑动窗口法分析及加法链在预计算中的应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第40卷第7期计算机工程2014年7月V_01．40NO．7ComputerEngineeringJuly2014·开发研究与工程应用·文章编号：1000—3428(2014)07—0263—04文献标识码：A中图分类号：TP309．2模幂滑动窗口法分析及加法链在预计算中的应用屈晓，孙达志t，(1．天津大学计算机科学与技术学院，天津300072；2．中国科学院信息工程研究所，北京100093)摘要：滑动窗口法是计算大数模幂问题应用最广泛的方法之一，然而针对此方法复杂度的精确理论分析却十分稀少。在计算效率方面，当窗口选择过大时，预计算培呈指数型增长。针对这2个

2、问题，利用马尔可夫状态转移矩阵对滑动窗171法进行效率分析，给出大数模幂计算在二进制编码下滑动窗口法的精确复杂度表示，其理论值与实际值在各情况下误差绝对值不超过0．1次模乘。同时提出一种利用加法链进行预计算的思想，给出一种计算机执行简单可行的求加法序列的算法，用于求解由多个给定值构成的加法链。实验结果证明，该算法能够提高窗门选择过大时的计算效率，并可用于同一信息的多方发送等。关键词：模幂；滑动窗口法；马尔可夫状态转移矩阵；精确复杂度；预计算；加法链；大窗口Analysis0fExp0nentiati0nSlidingWindowMethodandApplic

3、ationofAdditionChaininPrecomputationOUXiao1，SUNDa-zhiI，(1．Schoolel’ComputerScienceandTechnology，TianjinUniversity，Tianjin300072，China；2．InstituteofInformationEngineering，ChineseAcademyofSciences，Beijing100093，China)【Abstract】Slidingwindowmethodisoneofthemostwidelyusedmethodsforexpo

4、nentiation，butanalysisonitsexactcomputationalcomplexityarefew．Andwhenthewindowsizebecomesbigger，thetotalofprecomputationsgrowsexponentially．AnanalysisoftheexactcomplexityofslidingwindowmethodwithMarkovtransfermatrixispresented．Itpresentsanexpressionoftheexactcomplexityinbinarycode．

5、Thedifferencebetweentheorelicalandexperimentalvaluesislessthan0．1timeofmodularmultiplication．Afterthat，amethodwithadditionchainpassingallgivenvaluesinprecomputationisproposed．Itgeneratesanalgorithmwhichiscomputationallyfeasibleforcomputerimplementation．Experimentalresultshowsthatth

6、ismethodimprovestheeficiencygreatlywhenthewindowsizeisbig．Thisthoughtcanalsobeusedinthecaseoi’onemessagesendingtomanyclients．【Keywords】exponentiation；slidingwindowmethod；Markovstatetransfermatrix；exactcomplexity；precomputation；additionchain；bigwindowDo1：l0．3969／j．issn．1000—3428．201

7、4．07．0541概述本文首先对滑动窗口法的复杂度进行分析，利用马尔可夫链求出任意位任意窗口长度下的非零窗口数的一般表1978年RSA公钥密码算法被提出以来，公钥加密体制达式，然后提出一种应用于预计算部分的改进算法。逐步成为了信息安全领域应用最广泛的技术。模幂运算作为公钥体制的核心环节，其执行速度决定着公钥体制的总2基本方法体效率。然而计算机执行大数模幂运算速度慢这一问题，文献[1]总结了二进制法。二进制法将指数e表示成二进至今没有得到很好的解决。制串的形式：大数模幂运算最基本的方法是依次计算底数的各次模k一1e=(ek-1ek一2⋯eIeo)=∑e2幂值，

8、然而这种方法效率低下。目前已有许多关于大数模i=0幂