%0 Journal Article %A 韩文报 %A 李永光 %A 王广赛 %A 曾光 %T 基于k-ary消减的快速最大公约数算法 %D %R 10.11772/j.issn.1001-9081.2015.06.1673 %J 计算机应用 %P 1673-1677 %V 35 %N 6 %X

最大公约数(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算法的两倍。

%U http://www.joca.cn/CN/10.11772/j.issn.1001-9081.2015.06.1673