计算机应用 ›› 2015, Vol. 35 ›› Issue (6): 1673-1677.DOI: 10.11772/j.issn.1001-9081.2015.06.1673
收稿日期:
2015-01-05
修回日期:
2015-03-29
发布日期:
2015-06-12
通讯作者:
王广赛(1990-),男,河南鹿邑人,硕士研究生,CCF会员,主要研究方向:公钥密码;sswang1990@yeah.net
作者简介:
曾光(1980-),男,吉林吉林人,副教授,博士,主要研究方向:网络密码;韩文报(1963-),男,河北邯郸人,教授,博士生导师,主要研究方向:密码理论、网络安全;李永光(1988-),男,河南淮阳人,硕士研究生,主要研究方向:分组密码。
基金资助:
国家自然科学基金资助项目(61003291);数学工程与先进计算国家重点实验室开放课题基金资助项目(2013A03,2013A10)。
WANG Guangsai1,2, ZENG Guang1,2, HAN Wenbao1,2, LI Yongguang1,2
Received:
2015-01-05
Revised:
2015-03-29
Published:
2015-06-12
摘要:
最大公约数(GCD)算法中,对于输入B和C,利用Sorenson的右移k-ary消减思想提出一个算法用于寻找整数x和y,使得x和y满足Bx-Cy在二进制表示下低比特位部分为0,即Bx-Cy=0(mod 2e),其中e是常数正整数。利用该算法能够右移较多比特并大规模降低循环次数。再结合模算法,提出了快速GCD算法,其输入规模为n比特时最差复杂度仍然是O(n2),但最好的情况下复杂度能达到O(nlog2n log logn)。实验数据表明,对于20万以上比特规模的输入,快速GCD算法比Binary GCD算法速度快;对100万比特规模的输入,快速GCD算法速度是Binary GCD算法的两倍。
中图分类号:
王广赛, 曾光, 韩文报, 李永光. 基于k-ary消减的快速最大公约数算法[J]. 计算机应用, 2015, 35(6): 1673-1677.
WANG Guangsai, ZENG Guang, HAN Wenbao, LI Yongguang. Fast greatest common divisor algorithm based on k-ary reduction[J]. Journal of Computer Applications, 2015, 35(6): 1673-1677.
[1] BUCHBERGER B, JEBELEAN T. Parallel rational arithmetic for computer algebra systems: motivating experiments [M]. Vienna: ACPC-Austrian Center for Parallel Computation, 1993: 1-3.查不到该文献, 作者确认是否有误。书名[M].出版地:出版社, 出版年:引用页码。 [2] LIOYD E K. The art of computer programming, vol. 2, seminumerical algorithms[J]. Software: Practice and Experience, 1982, 12(9): 883-884. [3] STEIN J. Computational problems associated with Racah algebra [J]. Journal of Computational Physics, 1967, 1(3): 397-405. [4] BRENT R P, KUNG H T. Systolic VLSI arrays for polynomial GCD computation [J]. IEEE Transactions on Computers, 1984, C-33 (8): 731-736. [5] YAP C K. Fundamental problems in algorithmic algebra [M]. Oxford: Oxford University Press, 核实是2000版还是1999-2000: 43-76. [6] STEHLÉ D, ZIMMERMANN P. A binary recursive gcd algorithm [C]//Proceedings of the 2004 6th International Symposium on Algorithmic Number Theory , LNCS 3076. Berlin: Springer, 2004: 411-425. [7] SORENSON J. Two fast GCD algorithms [J]. Journal of Algorithms, 1994, 16(1): 110-144. [8] JEBELEAN T. A generalization of the binary GCD algorithm [C]//Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation. New York: ACM, 1993: 111-116. [9] WEBER K.The accelerated integer GCD algorithm [J]. ACM Transactions on Mathematical Software, 1995, 21(1): 111-122. [10] SEDJELMACI S M. The mixed binary Euclid algorithm [J]. Electronic Notes in Discrete Mathematics, 2009, 35查过, 无期: 169-176. [11] MOHAMED F K. A novel fast hybrid GCD computation algorithm [J]. International Journal of Computing Science and Mathematics, 2014, 5(1): 37-47. [12] COHN H. Advanced number theory [M]. New York: Courier Dover Publications, 网上是19802012: 55-56. [13] SCHÖNHAGE A, STRASSEN V. Schnelle multiplikation grosser zahlen [J]. Computing, 1971, 查不到卷期, 核实卷期7(3/4): 281-292. [14] BRENT R P. Analysis of the binary Euclidean algorithm [EB/OL]. [2014-12-02]. http://maths-people.anu.edu.au/~brent/pd/rpb037a.pdf. Pittsburgh: Department of Computer Science, Carnegie-Mellon University, 1976: 321-355. |
[1] | 张平, 贾亦巧, 王杰昌, 石念峰. 三因子匿名认证与密钥协商协议[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3281-3287. |
[2] | 庞晓琼, 杨婷, 陈文俊, 王云婷, 刘天野. 区块链环境下基于秘密共享的数字权限管理方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3257-3265. |
[3] | 巫光福, 戴子恒. 应对反应攻击的级联中密度准循环奇偶校验码公钥方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3274-3280. |
[4] | 李莉, 杨鸿飞, 董秀则. 基于身份多条件代理重加密的文件分级访问控制方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3251-3256. |
[5] | 郭丽峰, 王倩丽. 自适应安全的带关键字搜索的外包属性基加密方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3266-3273. |
[6] | 孙晓玲, 杨光, 沈焱萍, 杨秋格, 陈涛. 基于可拆分倒排索引的可搜索加密方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3288-3294. |
[7] | 孙晓玲 李姗姗 杨光 杨秋格. 基于差分表的Blow-CAST-Fish的密钥恢复攻击[J]. 计算机应用, 0, (): 0-0. |
[8] | 樊缤 李智 高健. 基于多尺度知识学习的深度鲁棒水印算法[J]. 计算机应用, 0, (): 0-0. |
[9] | 沈子懿, 王卫亚, 蒋东华, 荣宪伟. 基于Hopfield混沌神经网络和压缩感知的可视化图像加密算法[J]. 计算机应用, 2021, 41(10): 2893-2899. |
[10] | 巫光福, 王影军. 基于区块链与云-边缘计算混合架构的车联网数据安全存储与共享方案[J]. 计算机应用, 2021, 41(10): 2885-2892. |
[11] | 高健 李智 樊缤 姜传贤. 基于光线投射采样和四元数正交矩的高效三维医学图像鲁棒零水印算法 [J]. 计算机应用, 0, (): 0-0. |
[12] | 徐丽云, 闫涛, 钱宇华. 基于级联混沌系统的分数域语音加密算法[J]. 计算机应用, 2021, 41(9): 2623-2630. |
[13] | 陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585. |
[14] | 张永斌, 常文欣, 孙连山, 张航. 基于字典的域名生成算法生成域名的检测方法[J]. 计算机应用, 2021, 41(9): 2609-2614. |
[15] | 葛纪红, 沈韬. 基于区块链的能源数据访问控制方法[J]. 计算机应用, 2021, 41(9): 2615-2622. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||