欧几里得算法

Published: by Creative Commons Licence

  • Tags:

欧几里得算法

要求两个数的最大公约数,我们可以利用欧几里得算法实现。

//要求a >= b >= 0
gcd(a, b){
    if(b == 0){
        return a;
    }
    return gcd(b, a % b)
}

先来讨论正确性,设$g$是$a$和$b$的最大公约数,那么$a\mod b = a-kb=g(\frac{a}{g}-k\frac{b}{g})$,也是$g$的倍数。同理设$g'$是$b$和$a\mod b$的最大公约数,那么有$a=(a\mod b) + kb=g'(\frac{(a\mod b)}{g'}+k\frac{b}{g'})$,因此$g'$也是$a$的因子。结合这两条性质可以直接推出$g=g'$。因此我们可以借助计算$b$和$a\mod b$的最大公约数$g'$来得到$a$和$b$的最大公约数$g$。

之后来讨论时间复杂度,若$a\geq 2b$,那么$a\mod b<\frac{a}{2}$。否则$a<2b$,则$a\mod b\leq a - b<\frac{a}{2}$。因此不管哪种情况,较大的数在下次递归时都至少会减少一半。因此可以直接得出gcd递归调用的总次数为$O(\log ab)$,由于每次递归都是常数时间复杂度,因此这也就是我们要的时间复杂度。

由于$a$和$b$的最大公倍数等于$\frac{ab}{g}$,其中$g=gcd(a,b)$。因此我们可以直接推出最大公倍数算法:

//要求a >= b > 0
lcm(a, b){
    return a / gcd(a, b) * b; // 先除法后乘法的目的是防止乘法溢出
}

下面来了解以下欧几里得算法的性质。

欧几里得算法还有一个非常重要的特性,就是我们要计算$n$个数的最大公约数,实际时间复杂度应该是$O(n+\log_2M)$而不是$O(n\log_2M)$,其中$M$是这$n$个数中的最大值。

扩展欧几里得算法

扩展欧几里得算法可以帮助我们解决下面一类问题:

其中$a$和$b$已知,且$c=gcd(a,b)$。要求我们找到一对合法的$(x,y)$。

当$b=0$的时候,我们一定有$a\cdot 1 + b\cdot 0=c$,接下来考虑如果我们已知$bx+(a-kb)y=c$,其中$k=\lfloor\frac{a}{b}\rfloor$。可以得出

利用这个公式可以直接推出扩展欧几里得算法。

extgcd(a, b){
    if(b == 0){
        return {1, 0};
    }
    {x, y} = extgcd(b, a % b);
    return {y, x - a / b * y};
}

下面来了解以下扩欧算法的性质。

了解了扩展欧几里得原理后,我们可以利用它在模运算下求逆计算$x^{-1}$。对于模运算下求逆,如果模的数是素数,我们可以用费马小定理计算,其时间复杂度是严格$\Theta(\log_2p)$,其中$p$是模数。但是如果我们用扩展欧几里得算法来求逆,那得到的是$O(\log_2p)$,即上界为此,但是实际上扩展欧几里得算法会快得多(因此实践中辗转次数非常少),并且扩欧不要求$p$是素数,只要求$p$和$x$互质。

扩欧还有一个非常重要的性质,就是我们可以发现算法中出现了乘法和减法运算,那么是否有可能在计算过程中出现数值溢出而导致结果错误呢?事实上这是不可能的,我们可以证明除非$b=0$的情况,有$(x,y)=(1,0)$,其余情况下都满足$|x|<b$且$|y|<a$。这里给一下证明:

考虑上面算法回退的时候,第一次满足$b>c$,则此时{x, y} = extgcd(b, a % b);得到的$x=0,y=1$,此时一定满足条件。现在假设该行返回的结果$(x,y)$满足条件$|x|<a-kb,|y|<b$,那么我们接下来证明return {y, x - a / b * y};这一行返回的结果也满足条件。很显然$y<b$是已经成立的了,因此我们只需要证明$|x - ky|<a$即可。

由于$bx+(a-kb)y=c<b$,因此一定有$x>0$且$y<0$或$x<0$且$y>0$中的一方成立。

  • 如果$x>0$且$y<0$成立,则由于$y<0$此时$x-ky>0$一定成立,根据$x-ky<(a-kb)-ky<a-kb-kb=a$,因此有$|x - ky|<a$成立。
  • 如果$x<0$且$y>0$成立,则由于$y>0$此时$x-ky<0$一定成立,根据$x-ky>-(a-kb)-ky>-a+kb-kb=-a$,因此有$|x - ky|<a$成立。

可以发现任意情况下都有$|x - ky|<a$。根据归纳法可以证明结论。