Cryptography: The Extened Euclidean Algorithm

Important for later computations in the area of finite fields and in encryption algorithms, such as RSA

For given integers a and b, the extended Euclidean algorithm not only calculate the greatest common divisor d but also two additional integers x and y that satisfy the following equation.
                ax + by = d = gcd(a,b)
x and y will have opposite signs

Now let us show how to extend the Euclidean algorithm to determine (x, y, d) given a and b.
we assume that at each step i we can find integers xi and yi that satisfy ri = axi + byi.
We end up with the following sequence.

Now, we can rearrange terms to write ri = ri-2 - ri-1qi

Also, in rows i – 1 and i - 2, we find the values
ri-2 = axi-2 + byi-2 and ri-1 = axi-1 + byi-1

Substituting into ri, we have
ri = (axi-2 + byi-2) - (axi-1 + byi-1)qi

    = a(xi-2 – qi xi-1) + b(yi-2 – qi yi-1)

But we have already assumed that ri = axi + byi. Therefore,

  xi = xi-2 – qi xi-1 and yi = yi-2 – qi yi-1

In each row, we calculate a new remainder ri based on the remainders of the previous two rows, namely ri - 1 and ri - 2.

To start the algorithm, we need values for r0 and r- 1, which are just a and b.

It is then straightforward to determine the required values for x - 1, y- 1, x0, and y0.

We know from the original Euclidean algorithm that the process ends with a remainder of zero and that the greatest common divisor of a and b is d = gcd(a,b) = rn.

But we also have determined that d = rn = axn + byn.

As an example, let us use a=1759 and b=550 and solve for 1759x + 550y = gcd(1759, 550). The results are shown in Table below.

Thus, we have 1759 × (–111) + 550 × 355 = –195249 + 195250 = 1.