The Extended Euclidean Algorithm has several applications. In this post, I’ll show you a python implementation as well as some of its applications.

It is used to calculate the greatest common divisor (GCD) of two numbers and also calculates two numbers x and y such that ax + by = gcd(a,b).

In this post, I’ll give you a python implementation of this algorithm and explain some of its applications in cryptography.

## Table of Contents

## The Extended Euclidean Algorithm

The Euclidean Algorithm calculates the (GCD) between two numbers. You can find the explanation of how this algorithm works, together with a python implementation in this link.

In this case, we are interested in the extended version of that algorithm.

So, the extended Euclidean algorithm calculates three values:

- The GCD
- x and y such that ax + by = gcd(a,b)

To calculate x and y that satisfy the previous equation, we use the following formulas.

*x _{i} *=

*x*

_{i-2}–

*q*

_{i}x_{i-1}

*y _{i} *=

*y*

_{i-2}–

*q*

_{i}y_{i-1}

x_{-1} = 1, x_{0}=0, y_{-1}=0, y_{0}=1

So, at each iteration of the algorithm, we calculate the quotient q_{i}, and then use it to calculate x_{i} and y_{i}.

The last values of x_{i} and y_{i} will be the values of x and y. Notice these values are calculated before a%b = 0.

Let’s see the code.

## Python program for the Extended Euclidean Algorithm

```
def extended_euclidean_alg(a, b):
x = []
y = []
q_i = int(a/b)
x.append(0)
y.append(1)
x.append(1)
y.append(-q_i)
a, b = b, a % b
i=2
while(b>0):
r_i = a % b
q_i = int(a/b)
a, b = b, a % b
x.append(x[i-2] - q_i * x[i-1])
y.append(y[i-2] - q_i * y[i-1])
i += 1
print (x[i-1], y[i-1])
return (a, x[i-2], y[i-2])
```

In this case, I used a list to store all the values x_{i} and y_{i}, but this is not necessary. As a practice, you can modify the code below to use integer variables instead of a list.

You can test the previous function with the following python code.

```
if __name__=='__main__':
a = 1759
b = 550
d, x ,y = extended_euclidean_alg(a,b)
print (d,x,y)
print (f'{a}x{x} + {b}x{y} = {a*x + b*y} = gcd({a},{b}) = {d}')
```

## Applications

One of the applications of the Extended Euclidean Algorithm is to calculate the multiplicative inverse of a number.

We know that the algorithm gives the GCD of two numbers plus numbers x and y that satisfy the equation ax + by = gcd(a,b).

If gcd(a,b)=1, then y is the multiplicative inverse of b mod a. This means that b*y mod a =1.

In general, applying the extended Euclidean algorithm to the equation nx +by =d, if d=1, then y is the multiplicative inverse of b in Z_{n}. Source: Cryptography and Network Security by W. Stallings.

So, how is this applied in cryptography?

“The Rivest-Shamir-Adleman (RSA) algorithm is the most widely accepted approach in asymmetric cryptography. Asymmetric cryptography means that one key is used to encrypt and a different, but related one is used to decrypting the message.” You can read more at this link.

When using RSA, we need to calculate a private key and a public key.

The first steps of the RSA algorithm are as follows:

- Choose p, q, two prime numbers
- Calculate n = pq
- Calculate f(n) = (p-1)(q-1)
- Chose e such that gcd(f(n), e) = 1; 1 < e < f (n), and
- Chose d, such that ed mod f(n) = 1

Notice *e* and *d* are multiplicative inverses modulo f(n). f(n) is the Euler totient function.

If GCD(f(n), d) = 1, then d is relative prime to f(n), and using the extended Euclidean algorithm, we can calculate y=d, which is the multiplicative inverse of e modulo f(n).

In a similar way, the extended Euclidean algorithm is also applied in Elliptic Curve Cryptography (ECC) keys.

Some of the applications of ECC are:

- Encryption/Decryption
- Digital signatures
- Key exchange

These are just some of the applications of the extended Euclidean Algorithm.