扩展欧几里得算法

Extended Euclidean Algorithm (eGCD).

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:

$$
\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

1
2
3
4
5
6
7
8
9
10

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$.