扩展欧几里得算法 | Baeldung中文网

1. Introduction

In this tutorial, we’ll explain the extended Euclidean algorithm (EEA). It’s a tool widely used in cryptography and one of the fundamental algorithms in number theory. In addition to its recursive version, we’ll present its iterative variant.

2. Bézout’s Identity

Bézout’s identity states that the greatest common divisor (GCD) of any two integers is their linear combination. So, if is the GCD of and , then there exist integers and such that:

(1) $\begin{equation*} d = xa + yb \end{equation*}$

For example, if a=5 and b=3 , then d=GCD(5,3)=1 and:

$[1 = -1\cdot 5 + 2\cdot 3]$

The extended Euclidean algorithm (EEA) finds $\boldsymbol{x}$ and $\boldsymbol{y}$ , which are called Bézout’s coefficients of $\boldsymbol{a}$ and $\boldsymbol{b}$ . As we’ll see, EEA is a modification of the Euclidean algorithm for finding the GCD of two numbers.

2.1. Assumptions

In what follows, we’ll assume that and are both positive and that a > b . We lose no generality under those assumptions because:

$[\begin{aligned} GCD(a, b) &=&& GCD(|a|, |b|) \\ GCD(a, b) &=&& GCD(b, a) \\ GCD(a, 0) &=&& a \end{aligned}]$

which means that we can consider only the case $\boldsymbol{a \geq b > 0}$ :

If either of and is zero, then we output the other number as their GCD and set the corresponding coefficients to and .
If (or ) is negative, then we replace it with its absolute value.
Finally, we can switch and if .

3. The Euclidean Algorithm (EA)

The Euclidean algorithm (EA) finds the GCD of and by using the fact that:

$[GCD(a, b) = GCD(b, a\bmod b)]$

and applying Euclidean division until it gets zero as the remainder:

$[\begin{aligned} \underbrace{a}_{a_1} &=&& \underbrace{\left\lfloor\frac a b \right\rfloor}_{q_1}\cdot \underbrace{b}_{a_2} + \underbrace{(a \bmod b)}_{a_3} &&(1\leq a_3 < b)\\ a_2 &=&& q_2\ a_3 + a_4 &&(1 \leq a_4 < a_3)\\ \vdots \\ a_{n-3} &=&& q_{n-3} a_{n-2} +a_{n-1} && (1 \leq a_{n-1} < a_{n-2}) \\ a_{n-2} &=&& q_{n-2} a_{n-1} +a_{n} && (1 \leq a_{n} < a_{n-1}) \\ a_{n-1} &=&& q_{n-1} a_{n} +a_{n+1} && (1 \leq a_{n+1} < a_n) \\ a_{n} &=&& q_{n}a_{n+1} + 0 &&(a_{n+2}=0) \end{aligned}]$

The last nonzero remainder ( $\boldsymbol{a_{n+1}}$ ) is the GCD of $\boldsymbol{a}$ and $\boldsymbol{b}$ . As we see, the recursion is:

(2) $\begin{equation*} \begin{cases} a_1 = a\\ a_2 = b \\ a_k = q_k a_{k+1} + a_{k+2},& k>2 \end{cases} \end{equation*}$

where $q_k = \left\lfloor \frac{a_{k}}{a_{k+1}} \right \rfloor$ . We’ll find it useful to re-formulate the recursive rule so that we express the remainder in terms of the dividend and the divisor:

(3) $\begin{equation*} \begin{cases} a_1 = a\\ a_2 = b \\ a_{k+2} =a_k - q_k a_{k+1}, & k>2 \end{cases} \end{equation*}$

4. The Recursive Version of the Extended Euclidean Algorithm

The recursive extension of EA (REEA) runs just like the regular EA until it computes $a_{n+1}$ , the GCD of the input numbers and . At that point, it starts recursing back to the beginning, revisiting the division steps of $a_{n-1}, a_{n}, \ldots, a_2, a_1$ backward. After backtracking to a division step, REEA expresses the GCD as a combination of the step’s divisor and dividend.

So, from the second-to-last division, we get:

$[a_{n+1} = a_{n-1} -q_{n-1}a_{n} \\]$

Now, backtracking to $a_{n-2} = q_{n-2} a_{n-1} +a_{n}$ , we replace $a_{n}$ with $a_{n-2}-q_{n-2} a_{n-1}$ , so we have:

$[\begin{aligned} a_{n+1} &=&& a_{n-1} - q_{n-1}(a_{n-2}-q_{n-2}a_{n-1}) \\ &=&& (1+q_{n-1}q_{n-2})a_{n-1} +(- q_{n-1})a_{n-2} \end{aligned}]$

In general, let’s say we revisited the division step $a_{k+1} = q_{k+1} a_{k+2}+a_{k+3}$ and expressed $a_{n+2}$ as a linear combination of $a_{k+1}$ and $a_{k+2}$ :

(4) $\begin{equation*} a_{n+2} = x_{k+1} a_{k+1} + y_{k+1}a_{k+2} \end{equation*}$

Recursing one step back, we substitute $a_{k+2}$ with $a_k - q_k a_{k+1}$ in Equation (4):

(5) $\begin{equation*} \begin{aligned} a_{n+2} &=&& x_{k+1} a_{k+1} + y_{k+1}(a_k - q_k a_{k+1}) \\ & =&& \underbrace{y_{k+1}}_{x_k}a_k+ \underbrace{(x_{k+1}-y_{k+1} q_k)}_{y_k}a_{k+1} \end{aligned} \end{equation*}$

Therefore, we obtain the following backward recursive rules:

(6) $\begin{equation*} \begin{cases} x_{n-1} = 1 \\ y_{n-1} = -q_{n-1} \\ x_k=y_{k+1}, & 1 \leq k < n - 1 \\ y_k = x_{k+1}-y_{k+1} q_k, & 1 \leq k < n - 1 \end{cases} \end{equation*}$

We apply them going backward through the division steps until we finally represent the GCD as a linear combination of $\boldsymbol{a_1=a}$ and $\boldsymbol{a_2=b}$ :

algorithm RecursiveExtendedEuclideanAlgorithm(a, b):
    // INPUT
    //    a, b = two non-negative integers
    // OUTPUT
    //    d = the greatest common divisor (GCD) of a and b
    //    x, y = integers such that d = x * a + y * b

    if b = 0:
        d <- a
        x <- 1
        y <- 0
        
        return (d, x, y)
    
    q <- floor(a / b)
    r <- a mod b
    (d, x, y) <- RecursiveExtendedEuclideanAlgorithm(b, r)
    
    return (d, y, x - q * y)

4.1. Example

Let’s say that a=234 and b=44 . Applying the algorithm, we do five Euclidean divisions:

$[\begin{aligned} 254 &= 5\cdot 44 + 34 \\ 44 &= 1\cdot 34 + 10 \\ 34 &= 3\cdot 10 + 4 \\ 10 &= 2\cdot 4 + \boldsymbol{2}\\ 4 &= 2\cdot 2 + 0 \end{aligned}]$

Or, using recurrence (3):

$[\begin{aligned} 34 &= 254 - 5\cdot 44 \\ 10 &= 44 - 1 \cdot 34 \\ 4 &= 34 - 3 \cdot 10 \\ \boldsymbol{2} & = 10 - 2\cdot 4 \\ 0 &= 4 - 2\cdot 2 \end{aligned}]$

After identifying the GCD, we go backward one division step. From there, we get $2 = 1\cdot 10 + (-2)\cdot 4$ and climb one step up to see what to substitute with:

$[\begin{aligned} &\downarrow && 34 = 254 - 5\cdot 44 && & \\ &\downarrow && 10 = 44 - 1 \cdot 34 && & \\ &\downarrow && 4 = 34 - 3 \cdot 10 && 2 = 1\cdot 10 + (-2)\cdot (34 - 3\cdot 10) & \\ &\downarrow && 2 = 10 - 2\cdot4 && 2 = 1\cdot 10 + (-2)\cdot 4 & \uparrow \\ & && 0 = 4 - 2\times 2 && & \uparrow \\ \end{aligned}]$

After some elementary algebra, we get that $2 = (-2)\cdot 34 + 7 \cdot 10$ . Then, we go up a step again to see what to replace with:

$[\begin{aligned} &\downarrow && 34 = 254 - 5\cdot 44 && & \\ &\downarrow && 10 = 44 - 1 \cdot 34 && 2 = (-2)\cdot 34 + 7\cdot(44 - 1\cdot 34)& \\ &\downarrow && 4 = 34 - 3 \cdot 10 && 2 = (-2)\cdot 34 + 7\cdot 10 & \uparrow\\ &\downarrow && 2 = 10 - 2\cdot4 && 2 = 1\cdot 10 + (-2)\cdot 4 & \uparrow\\ & && 0 = 4 - 2\times 2 && & \uparrow \end{aligned}]$

and get $2 = 7 \cdot 44 + (-9)\cdot 34$ . In the end, we backtrack to the first division step:

$[\begin{aligned} &\downarrow && 34 = 254 - 5\cdot 44 && 2 = 7\cdot 44 - 9\cdot(254-5\cdot 44)& \\ &\downarrow && 10 = 44 - 1 \cdot 34 && 2 = 7\cdot 44 + (-9)\cdot 34 & \uparrow \\ &\downarrow && 4 = 34 - 3 \cdot 10 && $2 = (-2)\cdot 34 + 7\cdot 10 & \uparrow\\ &\downarrow && 2 = 10 - 2\cdot4 && 2 = 1\cdot 10 + (-2)\cdot 4 & \uparrow \\ &&& 0 = 4 - 2\times 2 && & \uparrow \end{aligned}]$

and obtain Bézout’s coefficients:

(7) $\begin{equation*} GCD(254, 44) = 2 = (-9)\cdot 254 + 52 \cdot 44 \end{equation*}$

5. The Iterative Version of the Extended Euclidean Algorithm

We can compute the coefficients without backtracking. The idea is to express each step’s remainder as a linear combination of $\boldsymbol{a_1=a}$ and $\boldsymbol{a_2=b}$ . To do so, we start by noting that:

$[\begin{aligned} a_1 &=&& \underbrace{1}_{x_1}\cdot a_1 + \underbrace{0}_{y_1} \cdot a_2 \\ a_2 &=&& \underbrace{0}_{x_2}\cdot a_1 + \underbrace{1}_{y_2} \cdot a_2 \end{aligned}]$

In general, we’ll have:

(8) $\begin{equation*} a_{k} = x_ka_1+y_ka_2 \end{equation*}$

and we want rules for calculating the coefficients in a step given those from the previous steps. As it turns out, we need only the coefficients from the previous two steps. So, let’s suppose that we know $x_{k}$ , $x_{k+1}$ , $y_{k}$ , and $y_{k+1}$ for some $k \geq 1$ :

$[\begin{aligned} a_{k} &=&& x_ka_1+y_ka_2 \\ a_{k+1} &=&& x_{k+1}a_1+y_{k+1}a_2 \end{aligned}]$

Using Equation (3), we get:

(9) $\begin{equation*} \begin{aligned} a_{k+2} &=&& a_{k} - q_k a_{k+1} \\ &=&& (x_ka_1+y_ka_2)-q_k(x_{k+1}a_1+y_{k+1}a_2) \\ &=&& \underbrace{(x_k-q_kx_{k+1})}_{x_{k+2}}a_1 + \underbrace{(y_k-q_ky_{k+1})}_{y_{k+2}}a_2 \end{aligned} \end{equation*}$

Hence, these are our forward recurrences for the coefficients:

(10) $\begin{equation*} \begin{cases} x_1 = 1\\ x_2 = 0\\ x_{k+2} = x_k - q_k x_{k+1}, & k \geq 1 \end{cases} \qquad \text{ and } \qquad \begin{cases} y_1 = 0\\ y_2 = 1\\ y_{k+2} = y_k - q_k y_{k+1}, & k \geq 1 \end{cases} \end{equation*}$

We start from $\boldsymbol{a_1}$ and $\boldsymbol{a_2}$ and gradually work our way through division steps until we calculate the GCD, at which point we also obtain the sought Bézout’s coefficients:

algorithm terativeExendedEuclideanlgorithm(a, ):
    // INUT
    //   a, b = two positive integers
    // OUTPUT
    //    d = the GCD of a and b
    //    x, y = the coefficients such that d = GCD(a, b) and d = xa + yb
    //    x``, x`, y``, and y` correspond to x_k, x_{k+1}, y_k, y_{k+1} in recurrences (10)
    
    x`` <- 1
    x`  <- 0
    y`` <- 0
    y`  <- 1
    
    while b > 0:
        q <- a div b
        r <- a mod b
    
        x <- x` - q * x``
        y <- y` - q * y``
    
        x`` <- x`
        x` <- x
        y`` <- y`
        y` <- y
    
        a <- b
        b <- r
    
    d <- a
    
    return (d, x, y)

This is how it’ll look like step by step:

iterative flowchart 2

This iterative form of the EEA is equivalent to the Blankinship method for two numbers, which extends EA to find the GCD and Bézout’s coefficients of $n \geq 2$ numbers, not just two.

5.1. Example

Let’s reuse the example for REEA. Here, we compute the coefficients as we perform Euclidean divisions. The first remainder, , is a direct linear combination of 254 and :

$[254 = 5\cdot 44 + 34 \implies 34 = 1\cdot 254 + (-5)\cdot 44 \\]$

Next, we divide with . Then, we express the remainder as a linear combination of and and replace with the expression we got in the previous step:

$[\begin{aligned} &\downarrow & 254 &=& 5\cdot 44 + 34 && 34 &=&& 1\cdot 254 + (-5)\cdot 44\\ & & 44 &=& 1\cdot 34 + 10 && 10 &=&& 44 - 1\cdot 34\\ & & && && 10 &=&& 44-1(254-5\cdot 44)\\ & & && && 10 &=&& (-1)\cdot 254+6\cdot 44 \\ \end{aligned}]$

We obtain the coefficients by repeating the step. After each division step, we express the remainder in terms of the current dividend and the divisor. Since both have appeared as remainders previously, we replace them with the corresponding linear combinations and simplify the expressions:

$[\begin{aligned} &\downarrow & 254 &=& 5\cdot 44 + 34 && 34 &= 1\cdot 254 + (-5)\cdot 44\\ &\downarrow & 44 &=& 1\cdot 34 + 10 && 10 &=(-1)\cdot 254+6\cdot 44 \\ &\downarrow & 34 &=& 3\cdot 10 + 4 && 4 &=34 - 3\cdot 10\\ &&&&&&4&=(1\cdot 254 - 5\cdot 44)-3(-254+6\cdot 44)\\ &&&&&&4&=4\cdot 254+(-23)\cdot 44\\ &&10 &=& 2\cdot 4 + 2 && 2 &= 1\cdot 10 + (-2)\cdot 4\\ &&&&&&2&= 1\cdot(-254+6\cdot 44)-2\cdot (4\cdot 254-23\cdot 44)\\ &&&&&&2&= (-9)\cdot 254 + 52\cdot 44 \end{aligned}]$

We get the same result as with REEA in the end, but without recursion. Generally, the iterative variant should be faster because it avoids recursive calls and keeps the same frame.

5.2. Speeding up the Algorithm

As we see from the recurrences (10), the -coefficients and -coefficients don’t depend on one another. Moreover, from the final form:

$[GCD(a, b) = x\cdot a + y \cdot b]$

we can calculate the final if we know the final :

$[y = \frac{GCD(a,b)-x\cdot a}{b}]$

and the other way around. So, there’s no need to compute both coefficients as we make division steps. That cuts the number of operations by a third.

6. How Many Coefficients Are There?

Bézout’s coefficients are not unique, In fact, if (x, y) is one pair of Bézout’s coefficients for and , then all the coefficients are of the form:

(11) $\begin{equation*} \left(x+k\left\lfloor\frac{a}{b}\right\rfloor, y + k\left\lfloor\frac{a}{b}\right\rfloor\right)\quad k \in Z \end{equation*}$

where d=GCD(a, b) .

Only two pairs satisfy:

(12) $\begin{equation*} (|x| \leq |b/d|) \land (|y| \leq |a/d|) \end{equation*}$

and EEA always finds one such pair.

7. Conclusion

In this article, we presented the recursive and iterative forms of the Extended Euclidean Algorithm. It’s used for finding Bézout’s coefficients of two integer numbers and has applications in cryptography.

Persistence

REST

Security