计算机应用 ›› 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. 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 Guangsai1,2, ZENG Guang1,2, HAN Wenbao1,2, LI Yongguang1,2   

  1. 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 Published:2015-06-12

摘要:

最大公约数(GCD)算法中,对于输入BC,利用Sorenson的右移k-ary消减思想提出一个算法用于寻找整数xy,使得xy满足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消减, 整数最大公约数算法

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(mod2e) 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(n2).In the best case, the complexity of the proposed algorithm could achieve O(nlog2 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

中图分类号: