Extended Euclidean Algorithm

By Sudheer S

August 17, 2024

Introduction

In this series of articles about number theory and cryptography, we have discussed

The Euclidean algorithm to compute the GCD for two integers a and b
The Bezout’s Identity: ax + bc = GCD(a,b)

This article will introduce the reader to the Extended Euclidean algorithm to compute the coefficients of the Bezout’s Identity.

Bézout’s identity states that for any two integers a and b, their greatest common divisor (GCD) can be expressed as:

GCD(a,b)=ax+by

where x and y are integers known as the coefficients of Bézout’s identity.

The math. TBD.

Division Algorithm

The division algorithm states that for any two integers a and b (with b non-zero), there exist unique integers q (the quotient) and r (the remainder) such that:

a=b×q+r

where:

a is the dividend
b is the divisor
q is the quotient,
r is the remainder, which satisfies 0≤r<∣b|

We can rearrange it to solve for the remainder r:

r=a−b×q

This equation tells us that the remainder is what’s left after subtracting the product of the divisor and the quotient from the dividend.

Here’s an implementation of the Euclidean algorithm using the equation r=a-bxq.

def gcd_iterative(a, b):

    # Initial values
    old_r, r = a, b  # r represents the remainder
    
    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        # the expression r = old_r - quotient * r equates to the mathematical expression: r = a - b*q
        # old_r amouunts to a and r amounts to b
    return old_r

# Example usage:
a = 252
b = 198
gcd = gcd_iterative(a, b)

print(f"GCD of {a} and {b} is {gcd}")

In the loop, old_r represents a of the mathemtical equation r = a - b*q. And r represents b. This is the essence of the Euclidean algorithm to compute the GCD.

This program is slightly different than our first version. In this version, we do not use the modulo operator. We explicitly determine the integer quotient using the expression old_r // r. We will soon make use of the quotient to compute the coefficenets of the Bezout’s identity.

Like I said in the previos post, the best way to thoroughly understand the program is to evaluate the steps using a pen and paper.

Proof Of The Euclidean Algorithm

As 0 ≤ r_i+1 < |r_i|, the sequence of the r_i is a decreasing sequence of nonnegative integers (from i = 2 on). Thus it must stop with some r_k+1 = 0.

This proves that the algorithm stops eventually.

Here, the loop index is 0 before the loop starts. At this point, r_i = r₀ = a. With each loop iteration, the remainder r decreases. With each iteration, the remainder is getting smaller and smaller.

This is denoted by;

r_i+1 < |r_i|

eventually, r becomes 0.

The mathematial notation:

0 ≤ r_i+1 < |r_i|

As r_i+1 = r_i-1 - r_iq_i (By definition of the algorithm) the greatest common divisor is the same for (r_i-1, r_i) and (r_i, r_i+1)

The greaterst common divisor of the input a = r₀, b = r₁ is the same as r_k,r_k+1. When the algorithm r_k+1=0. Hence, r_k is the greatest common divisor of a and b.

The Extended Euclidean Algorithm

Building on the Euclidan algorithm, let’s implement the extended Euclidean algorithm to compute the coefficients of the Bezout’s identity.


def extended_gcd_iterative(a, b):
    print(f"The start of the function a = {a} and b = {b}")
    # Initial values
    old_r, r = a, b  # r represents the remainder
    old_x, x = 1, 0  # Coefficients for a
    old_y, y = 0, 1  # Coefficients for b
    
    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r # the same as in the Eucildean algorithm

        old_x, x = x, old_x - quotient * x 
        # x: This represents the current coefficient for a in the linear combination.
        # old_x: This represents the previous coefficient for a from the last iteration.
        old_y, y = y, old_y - quotient * y
        
    # old_r is the GCD, and old_x and old_y are the coefficients
    return old_r, old_x, old_y

# Example usage:
a = 252
b = 198
gcd, x, y = extended_gcd_iterative(a, b)

print(f"GCD of {a} and {b} is {gcd}")
print(f"Coefficients of Bézout's Identity: x = {x}, y = {y}")
print(f"Bézout's Identity: {gcd} = {x} * {a} + {y} * {b}")

Output Of The Program

GCD of 252 and 198 is 18
Coefficients of Bézout's Identity: x = 4, y = -5
Bézout's Identity: 18 = 4 * 252 + -5 * 198

Setting Initial Values:

old_x and x:

old_x = 1: This represents the initial coefficient for a when we start the algorithm.

x = 0: This is the initial coefficient for b.

When the algorithm starts, we haven’t yet performed any operation. The equation a=1×a+0×b clearly holds, which corresponds to old_x = 1 and x = 0.

old_y and y:

old_y = 0: This represents the initial coefficient for a when we start the algorithm.

y = 1: This is the initial coefficient for b.

Similarly, b=0×a+1×b is true initially, which corresponds to old_y = 0 and y = 1.

Role of x and old_x:

x: This represents the current coefficient for a in the linear combination.
old_x: This represents the previous coefficient for a from the last iteration.

During the execution of the algorithm, we need to update these coefficients to reflect the new linear combination that results from the Euclidean step.

When you apply the division step in the Euclidean algorithm: remainder = old_r − quotient × r

you are essentially saying that the new remainder is a linear combination of a and b, but this combination involves different coefficients than before. To maintain the relationship GCD(a,b)=ax+by throughout the iterations, the coefficients must be updated accordingly.

Updating The Coefficient `x`:

The formula old_x, x = x, old_x - quotient * x updates the coefficient x as follows:

Shift the Current Coefficient:

old_x is set to x.

This effectively shifts the current coefficient for a into the position of the “old” coefficient, preparing it for the next iteration.

Compute the new Coefficient:

x is updated to old_x - quotient * x.

old_x represents the coefficient of a before this iteration. quotient is the quotient obtained from dividing the current pair of remainders. x represents the coefficient of a in the current iteration. The term quotient * x adjusts the coefficient by the number of times the divisor (represented by r) fits into the dividend (represented by oldr_r). Subtracting this product from old_x gives the correct coefficient for the remainder after the current step.

Proof Of The Extended Euclidean Algorithm

Continuing from the proof of the Euclidean algorithm, we have:

r_i+1 = r_i-1 - r_i * q_i

Divide the old remainder by the current remainder. This gives us the quotient. Plug the values into the division algorithm equation. We get r_i+1 = r_i-1 - r_i * q_i.

From the Bezout’s identity we have: r = ax + by.

Therefore, r_i = ax_i + by_i and r_i-1 = ax_i-1 + by_i-1 and r_i+1 = ax_i+1 + by_i+1 and so on.

Substituting these values in to the equation r_i+1 = r_i-1 - r_i * q_i

= ax_i-1 + by_i-1 - (ax_i+ by_i) * q_i

= ax_i-1 + by_i-1 - ax_iq_i - by_iq_i

= (ax_i-1 - ax_iq_i) + (by_i-1 - by_iq_i)

= ax_i+1 + by_i+1

Therefore x_k and t_k are the Bezout cofficients. Notice that r_k+1 = 0. r_k is the the GCD, ie the last non zero remainder.

The Computational Complexity

The computational complexity of the extended Euclidean algorithm is the same as the Euclidean algorithm, ie, O(log⁡(min⁡(a,b))). We are just performing a couple of extra lines of computation within the same loop. The overhead of calculating the coefficients x and y is minimal. For an explanation of the time complexity of the Euclidean algorithm please read the prevous article in the series.