最短加法链的一种快速算法  

A fast algorithm for shortest addition chains

作　　者：吴金霞[1] 吴乘先 韦康 刘博 李金玲 WU Jinxia;WU Chengxian;WEI Kang;LIU Bo;LI Jinling(College of Science,Liaoning University of Technology,Jinzhou 121001,China;School of Electronic&Information Engineering,Liaoning University of Technology,Jinzhou 121001,China)

机构地区：[1]辽宁工业大学理学院,辽宁锦州121001 [2]辽宁工业大学电子与信息工程学院,辽宁锦州121001

出　　处：《沈阳师范大学学报（自然科学版）》2019年第5期423-427,共5页Journal of Shenyang Normal University:Natural Science Edition

基　　金：辽宁省教育厅高校基本科研项目(JQL201715409)

摘　　要：针对可计算n的最短加法链问题,提出了一种快速算法,利用贪心算法思路,从1开始不断翻倍,当翻倍后大于n时,进行向前遍历,使得结果小于等于n,在此基础上利用深度优先搜索算法得到当前可行解及其深度d,深度超过d时对当前分支不再进行搜索以减少空间复杂度,但是当加法链扩散出去后时间复杂度上会呈指数增长,所以再结合一些剪枝函数,进行剪枝操作以减少时间复杂度,进而在一个有效时间内得到较好的解。针对7类挑战问题,利用Eclipse平台编写改进算法,给出具有最短加法链长度的数及其加法链表示;加法链能应用到模指数的幂运算中,而模指数的幂运算是公钥密码学中的核心运算之一,因此改进最短加法链的快速算法可以提高公钥密码体制的执行速度。For the shortest addition chains considering integer n,an improved fast algorithm is proposed,which uses the greedy algorithm idea to doubling from 1.When it is more than n after doubling,it traverses forward,so that the result is less than or equal to n.Based on the Depth-First-Search algorithm,the current feasible solution and its depth d are obtained.When the depth exceeds d,the current branch is no longer searched to reduce the space complexity,but the time complexity will increase exponentially when the additive chain is diffused.Combined with some pruning functions,the pruning operation is performed to reduce the time complexity,and then a better solution is obtained in an effective time.For the seven types of challenges,the improved algorithm is written by the Eclipse platform,and the number and its addition chain representation is given.The addition chain can be applied to modular exponentiation which is one of the core operations in public key cryptography,so the improved fast algorithm of shortest addition chain can improve the speed of execution of the public key cryptography.

关 键 词：最短加法链 贪心算法 深度优先 剪枝 

分 类 号：O29[理学—应用数学]