扩展欧几里得算法

Extended Euclidean Algorithm (eGCD).

Euclidean Algorithm (辗转相除法) is one of the oldest and most widely known algorithms. It is a $O(\log n)$ method of computing the greatest common divisor (GCD) of two integers $a,b$ .

According to Bezout's Identity, there exists integers $X$ and $Y$ that $Xa+Yb=\gcd(a,b)$ given $a,b$ . The extended Euclidean algorithm is the method of computing such $X$ and $Y$ .

Assuming two adjacent levels in the GCD recursive process:

current $X$	current $Y$	current $a$	current $b$
unknown $X$	unknown $Y$	$a$	$b$
known $X'$	known $Y'$	$b$	$a\% b$

\begin{aligned} Xa+Yb&=X'b+Y'(a\% b) \\ Xa+Yb&=X'b+Y'(a-\lfloor \frac{a}{b}\rfloor b) \\ Xa+Yb&=Y'a+(X'-Y'\lfloor \frac{a}{b} \rfloor)b \\ \end{aligned}

Therefore $X=Y', Y=X'-Y'\lfloor \frac{a}{b} \rfloor$ .

Code Implementation

cpp

int exgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int gcd = exgcd(b, a % b, x, y);
    int _x = x;
    x = y, y = _x - y * a / b;       // from the above equities
    return gcd;
}

Using eGCD to get Inverse

Given $b,N$ , if $\gcd(b,N)=1$ , $b$ is invertible modulo $N$ . We could apply eGCD algorithm to find multiplicative inverse of $b$ modulo $N$ .

Run the above function exgcd(b,N,x,y), we could obtain $x$ and $y$ that $xb+yN=\gcd(b,N)=1$ . Therefore $xb\equiv 1 \pmod{N}$ . $x$ is a multiplicative inverse of $b$ modulo $N$ .

Eureka moment!

不得不感叹聪明的人与时代无关。这一这么古老的算法也花了我一段时间去弄懂。

无论是 GCD 还是 exGCD，其核心在于欧几里得公式 $\gcd(a,b)=\gcd(b,a\%b)$ . exGCD 只是在这一基础上结合了裴蜀定理递推计算对应的 $x$ 和 $y$ 。

这里提供一个非正式的证明：首先是一个基本事实：对于互质的 $\langle k_1,k_2 \rangle$ ， $\langle k_1\% k_2, k_2\rangle$ 也一定互质。这一为了方便用群论的知识做个解释： $\gcd(k_1,k_2)=1$ , 所以 $k_1 \in (\mathbb{Z}/k_2)^{*}$ 。自然 $k_1\% k_2 \in (\mathbb{Z}/k_2)^{*}$ ，所以 $\gcd(k_1\% k_2,k_2)=1$ 。

那么对于任意正整数 $a,b$ ，设 $d=\gcd(a,b)$ ，则有 $a=k_1d, b=k_2d$ ，且 $\gcd(k_1,k_2)=1$ . 那么 $a\%b=a-\lfloor \frac{a}{b} \rfloor b=a-\lfloor \frac{k_1}{k_2} \rfloor b=k_1d- \lfloor \frac{k_1}{k_2} \rfloor k_2d=(k_1\% k_2)d$ 。根据上面的事实，我们有 $\gcd(k_2,k_1\% k_2)=1$ ，所以 $\gcd(b, a\%b)=d\gcd(k_2, k_1\% k_2)=d$ 。