计算机科学 ›› 2015, Vol. 42 ›› Issue (3): 228-232.doi: 10.11896/j.issn.1002-137X.2015.03.047
江顺亮,许庆勇,黄 伟,叶发茂,徐少平
JIANG Shun-liang, XU Qing-yong, HUANG Wei, YE Fa-mao and XU Shao-ping
摘要： 幂树法是求解最短加法链的一种简单近似方法,其计算效率高,一次可获得大量结果,但是精度偏低。随机幂树方法在扩展幂树时保持一层一层扩展,同时随机地扩展叶子结点,重复生成随机幂树并更新最优结果,在保持计算效率高的同时极大改善了计算精度。对于所有n<24924的数,通过9次重复生成随机幂树,准确率可达95%以上,平均达到97%,而且确保结果是次优结果。该方法在普通计算机上的求解规模可达155691199。
| [1] 周平,寇应展,王韬,等.一种改进的针对滑动窗口模幂运算实现的密码数据Cache计时攻击[J].计算机科学,2013,0(3):201-205 [2] Nedjah N,de Macedo Mourelle L.High-performance SoC-based implementation of modular exponentiation using evolutionary addition chains for efficient cryptography[J].Applied Soft Computing,2011,11(7):4302-4311 [3] Bleichenbacher D,Flammenkamp A.An efficient algorithm forcomputing shortest addition chains.http://www.homes.uni-bielefeld.de/ achim /addition_chain.html,1997 [4] Zhu Da-xin,Wang Xiao-dong.An Efficient Algorithm for Optimal Addition Chains[J].TELKOMNIKA, 2013,11(11):6447-6453 [5] Clift N M.Calculating optimal addition chains[J].Computing,2011,91:265-284 [6] Knuth D E.The art of computer programming:seminumericalalgorithms(3rd ed)[M].Addison-Wesley,Reading,1997:461-485 [7] Thurber E G.Efficient generation of minimal length additionchains[J].SIAM J Comput,1999,28:1247-1263 [8] Bahig H M.Star reduction among minimal length addition chains[J].Computing,2011,91:335-352 [9] 瞿云云,包小敏,刘花,等.大整数模幂的固定基窗口组合算法[J].计算机应用研究,2013,0(3):679-681 [10] Adan J,Hillel R M,Cindy G,et al.A Simulated Annealing Algorithm for the Problem of Minimal Addition Chains[C]∥ EPIA’11 Proceeding of the 15th Protugese Conference on Progress in Artificial Intelligence:Lecture Notes in Computer Science.2011:311-325 [11] Saúl D I,Efrén M M,Luis Guillermo O H.Addition chain length minimization with evolutionary programming[C]∥GECCO ’11 Proceedings of the 13th Annual Conference Companion on Genetic and Evolutionary Computation.ACM New York,NY,USA.2011:59-60 |
| No related articles found! |
|
||
首页