Computer Science ›› 2015, Vol. 42 ›› Issue (3): 228-232.doi: 10.11896/j.issn.1002-137X.2015.03.047

Previous Articles     Next Articles

Randomized Power Tree Method for Shortest Addition Chains

JIANG Shun-liang, XU Qing-yong, HUANG Wei, YE Fa-mao and XU Shao-ping   

  • Online:2018-11-14 Published:2018-11-14

Abstract: The power tree method is a simple addition chain approximation method for shortest addition chains with its high computing efficiency and ability to generate multi-results by single running,and unfortunately its accuracy is poor.Randomized power tree method improves calculation accuracy significantly while maintaining high efficiency.The methodextends nodes randomly one layer by one layer,and updates the better results by multi-running.For all numbers of n less than 24924,accuracy rate above 95% with an average of 97% was achieved by nine times running,while guarante-eing that the result is suboptimal.The solved problem is up to 155691199 scale by ordinary desktop PC.

Key words: Shortest addition chain,Power tree method,Randomized algorithms,Approximation algorithms

[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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!