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

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