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

• 作者: 刘博 吴乘先 吴金霞 李金玲 韦康
• 来源期刊: 沈阳师范大学学报（自然科学版）
• 学科: 数学
• 关键词: 最短加法链 贪心算法 深度优先 剪枝
• 年，卷（期）: 2019,（5）
• 所属期刊栏目: 计算数学
• 页码范围: 423-427
• 页数: 5页
• 分类号: O29
• 字数: 1628字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-5862.2019.05.008

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘博	辽宁工业大学理学院	2	8	1.0	2.0
2	吴金霞	辽宁工业大学理学院	7	4	1.0	2.0
3	吴乘先	辽宁工业大学电子与信息工程学院	1	0	0.0	0.0
4	韦康	辽宁工业大学电子与信息工程学院	1	0	0.0	0.0
5	李金玲	辽宁工业大学理学院	1	0	0.0	0.0