科研之友
微信
新浪微博
Facebook
分享链接
摘要
针对可计算n的最短加法链问题,提出了一种快速算法,利用贪心算法思路,从1开始不断翻倍,当翻倍后大于n时,进行向前遍历,使得结果小于等于n,在此基础上利用深度优先搜索算法得到当前可行解及其深度d,深度超过d时对当前分支不再进行搜索以减少空间复杂度,但是当加法链扩散出去后时间复杂度上会呈指数增长,所以再结合一些剪枝函数,进行剪枝操作以减少时间复杂度,进而在一个有效时间内得到较好的解。针对7类挑战问题,利用Eclipse平台编写改进算法,给出具有最短加法链长度的数及其加法链表示;加法链能应用到模指数的幂运算中,而模指数的幂运算是公钥密码学中的核心运算之一,因此改进最短加法链的快速算法可以提高公钥密码体制的执行速度。
-
单位辽宁工业大学
