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

来源：计算机应用杂志2015年第6期北京时间：

作者：王广赛, 曾光, 韩文报, 李永光

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

摘要：最大公约数(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消减,整数最大公约数算法

基金资助：国家自然科学基金资助项目(61003291);数学工程与先进计算国家重点实验室开放课题基金资助项目(2013A03,2013A10)。