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

发布时间：2021-09-06 23:08

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

【文章来源】：沈阳师范大学学报(自然科学版). 2019,37(05)

【文章页数】：5 页

【文章目录】：
0 引 言
1 贪心算法
2 深度优先搜索算法
3 剪枝函数与优化
4 结果分析
5 结 论


【参考文献】：
期刊论文
[1]基于最短加法链状态空间树的IAPWS-IF97快速计算方法[J]. 芮嘉敏,孙振业,程懋华.  汽轮机技术. 2017(04)
[2]最短加法链的随机幂树方法[J]. 江顺亮,许庆勇,黄伟,叶发茂,徐少平.  计算机科学. 2015(03)
[3]几种方幂模快速算法的加法链一致性分析[J]. 董付国,厉玉蓉.  计算机工程与应用. 2010(36)
[4]最短加法链算法[J]. 王晓东.  小型微型计算机系统. 2001(10)



本文编号：3388359