基于k-ary消减的快速最大公约数算法

doi:10.11772/j.issn.1001-9081.2015.06.1673

计算机应用 ›› 2015, Vol. 35 ›› Issue (6): 1673-1677.DOI: 10.11772/j.issn.1001-9081.2015.06.1673

基于k-ary消减的快速最大公约数算法

王广赛^1,2, 曾光^1,2, 韩文报^1,2, 李永光^1,2

1. 信息工程大学, 郑州 450001;
2. 数学工程与先进计算国家重点实验室, 郑州 450001

收稿日期:2015-01-05 修回日期:2015-03-29 发布日期:2015-06-12
通讯作者: 王广赛(1990-),男,河南鹿邑人,硕士研究生,CCF会员,主要研究方向:公钥密码;sswang1990@yeah.net
作者简介:曾光(1980-),男,吉林吉林人,副教授,博士,主要研究方向:网络密码;韩文报(1963-),男,河北邯郸人,教授,博士生导师,主要研究方向:密码理论、网络安全;李永光(1988-),男,河南淮阳人,硕士研究生,主要研究方向:分组密码。
基金资助:
国家自然科学基金资助项目(61003291);数学工程与先进计算国家重点实验室开放课题基金资助项目(2013A03,2013A10)。

Fast greatest common divisor algorithm based on k-ary reduction

WANG Guangsai^1,2, ZENG Guang^1,2, HAN Wenbao^1,2, LI Yongguang^1,2

1. Information Engineering University, Zhengzhou Henan 450001, China;
2. State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou Henan 450001, China

Received:2015-01-05 Revised:2015-03-29 Online:2015-06-12

摘要/Abstract

摘要：

最大公约数(GCD)算法中,对于输入B和C,利用Sorenson的右移k-ary消减思想提出一个算法用于寻找整数x和y,使得x和y满足Bx-Cy在二进制表示下低比特位部分为0,即Bx-Cy=0(mod 2^e),其中e是常数正整数。利用该算法能够右移较多比特并大规模降低循环次数。再结合模算法,提出了快速GCD算法,其输入规模为n比特时最差复杂度仍然是O(n²),但最好的情况下复杂度能达到O(nlog²n log logn)。实验数据表明,对于20万以上比特规模的输入,快速GCD算法比Binary GCD算法速度快;对100万比特规模的输入,快速GCD算法速度是Binary GCD算法的两倍。

关键词: 最大公约数算法, 欧几里得算法, 二进制最大公约数算法, 右移k-ary消减, 整数最大公约数算法

Abstract:

Greatest Common Divisor (GCD) is one of the basic subjects in computational number theory. It has a wide application in encryption and analysis of cryptography. For inputing B and C, an algorithm based on right-shift k-ary reduction proposed by Sorenson was presented for finding the integers x and y which satisfy the least significant bits of Bx-Cy were 0,i.e., Bx-Cy=0(mod2^e) where positive integer e was a constant. It could do a lot of right shifts and reduce a large number of cycles with taking advantage of the algorithm for finding the integers x and y. A fast GCD algorithm was proposed combined with modulus algorithm. When the size of the input was n bits, the worst complexity of the fast GCD algorithm was still O(n²).In the best case, the complexity of the proposed algorithm could achieve O(nlog² nlog logn). The experimental data show that actual implementations given input about more than 200000 bits, the fast GCD algorithm is faster than the Binary GCD algorithm, and the fast GCD algorithm is twice as fast as the Binary GCD algorithm for 1 million bits of input.

Key words: Greatest Common Divisor (GCD) algorithm, Euclidean algorithm, binary Greatest Common Divisor (GCD) algorithm, right-shift k-ary reduction, integer greatest common divisor algorithm

中图分类号:

TP309

王广赛, 曾光, 韩文报, 李永光. 基于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]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	高瑞, 陈学斌, 张祖篡. 面向部分图更新的动态社交网络隐私发布方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3831-3838.
[3]	项勇, 李艳俊, 黄丁韫, 陈愚, 谢惠琴. 全轮Shadow算法的差分和线性特征分析[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3839-3843.
[4]	赵振皓, 张仕斌, 万武南, 张金全, 秦智. 基于信誉值和强盲签名算法的委托权益证明共识算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3717-3722.
[5]	王伊婷, 万武南, 张仕斌, 张金全, 秦智. 基于SM9算法的可链接环签名方案[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3709-3716.
[6]	梁静, 万武南, 张仕斌, 张金全, 秦智. 面向主从链的慈善系统溯源存储模型[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3751-3758.
[7]	刘德渊, 张金全, 张鑫, 万武南, 张仕斌, 秦智. 基于无证书签密的跨链身份认证方案[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3731-3740.
[8]	张鑫, 张金全, 刘德渊, 万武南, 张仕斌, 秦智. 基于身份代理重加密的跨链身份管理方案[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3723-3730.
[9]	邓伊琳余发江. 基于LSTM和可分离自注意力机制的伪随机数生成器[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	张润莲王蒿唐瑞锋武小年. 基于均匀流型逼近与投影的高级加密标准算法相关功耗分析方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	刘运东汪学明. 基于穿刺伪随机函数的动态可搜索加密方案[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	张宏扬张淑芬谷铮. 面向个性化与公平性的联邦学习算法fedPF[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[13]	姚梓豪马自强李扬魏良根. 基于冲突的缓存侧信道攻击与驱逐集研究综述[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[14]	晏燕李飞飞吕雅琴冯涛. 安全高效的混洗差分隐私频率估计方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[15]	彭海洋计卫星刘法旺. 基于区块链的自动驾驶仿真测试数据存证模型[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.

基于k-ary消减的快速最大公约数算法

Fast greatest common divisor algorithm based on k-ary reduction

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics