Extended Euclidean Algorithm

The extension of standard Euclid algorithm is the Extended Euclidean algorithm. This algorithm computes the greatest common divisor (gcd) of two numbers and expresses the result (greatest common divisor) as a linear combination of the numbers used to calculate the gcd. The algorithm does not make use of factorization to compute the gcd of the numbers and is incredibly fast, even on extremely large numbers with thousands of digits.

In the context of computer algorithms, many textbooks consider recursive algorithms better than iterative ones. It is easy to establish the correctness of Recursive algorithms than the iterative version, forming the basis of the reason behind the previous theory. The recursive and iterative versions of extended Euclid’s algorithm vary up to a great degree. In most of the journals and publications, either the recursive or iterative version of an algorithm is presented, but not both. For example, the numbers involved are of hundreds of bits in length in case of implementation of RSA cryptosystems. In such cases, a recursive algorithm may be unacceptably slow. Let’s go through the basic concepts and implementation of standard and extended Euclidean algorithm.

1. Euclid’s Algorithm

Let’s say i1 and i2 are the largest integer that divides both i1 and i2. The Basic Euclidean Algorithm is a way to quickly find the greatest common divisor of integer i1 and i2. The time complexity of Euclid’s Algorithm is O (log min (i1, i2)).

1.1 Steps to follow:

The Euclid’s Algorithm for finding GCD (i1, i2) is as follows:

1. If i1 = 0 then GCD (i1, i2) = i2, since the GCD (0, i2) = i2, end the program.
2. If i2 = 0 then GCD (i1, i2) = i1, since the GCD (i1, 0) = i1, end the program.
3. Write i1 in quotient remainder form (i1 = i2⋅Q + R)
4. Find GCD of i2 and R using the Euclidean Algorithm. Also, we know that GCD (i1, i2) = GCD (i2, R)

1.2 Example

Let i1 = 250, i2 = 30.
250 = 30·8 + 10	  	gcd(250, 30) = gcd(30, 10)
30 = 10·3 + 0	  	gcd(30, 10) = 10
Therefore, gcd(250, 30) = 10.
Let i1 = 420, i2 = 45.
420 = 45·9 + 15	  	gcd(420, 45) = gcd(45, 15)
45 = 15·3 + 0	  	gcd(45, 15) = 15
Therefore, gcd(420, 45) = 15.
Let i1=2530, i2 = 56
2530 = 56.45 + 10 gcd(2530, 56) = gcd(56, 10) 
56 = 10.5 + 6  gcd(56, 10) = gcd(10, 6)
10 = 6.1 + 4  gcd(10, 6) = gcd(6, 4)
6 = 4.1 + 2   gcd(6, 4) = gcd(4, 2)
4 = 2.2 + 0   gcd(4, 2) = 2
Therefore, gcd(2530, 56) = 2

1.3 Euclid’s Algorithm using C Programming

PROGRAM:

#include < stdio.h >
// Function to calculate greatest common divisor of i1 and i2
int basic_euclid(int i1, int i2)
{
	if (i1 == 0)
		return i2;
	return basic_euclid(i2%i1, i1);
}
// Program to implement Euclid’s Algorithm.
int main()
{
	int i1 = 25, i2 = 35;
	printf("basic_euclid(%d, %d) = %d\n", i1, i2, basic_euclid(i1, i2));
	i1 = 15, i2 = 10;
	printf("basic_euclid(%d, %d) = %d\n", i1, i2, basic_euclid(i1, i2));
	i1 = 18, i2 = 24;
	printf("basic_euclid(%d, %d) = %d\n", i1, i2, basic_euclid(i1, i2));
	return 0;
}

OUTPUT: 
basic_euclid(25, 35) = 5
basic_euclid(15, 10) = 5
basic_euclid(18, 24) = 6

1.4 Applications of Euclid’s Algorithm

1. Laurent series. One possible implementation of Euclid’s algorithm is the approximation of formal Laurent series.
2. Linear Algebra and Orthogonal Polynomials. The Euclid’s algorithm can be applied in the domain of Linear Algebra and Orthogonal Polynomials as well. The interpolation conditions for the MPR (Minimal Partial Realization) problem in a linearized form can be written using Hankel system of equations.
3. Eigenvalue problem. The Euclidean Algorithm may also bring a solution to overcome Eigenvalue problem and implementing Linear systems. The triple (A, B, C) in the case of a linear system is called a state space realization of the system. When the number n which is the dimension of the state A is the smallest possible one to describe the input-output behaviour of the system, the realization is called minimal.
4. Coding Theory. One of the classical application of the Euclidean algorithm is found in the domain of error correcting codes, more precisely Goppa codes. Two examples are BCH codes and Reed-Solomon codes. To find linear feedback shift register realizations, the Berlekamp and Massey algorithm (BMA) was developed in order for the use of the associated system. This makes it somewhere equivalent to the Euclidean algorithm.
5. Rational approximation. While calculating rational approximations, the completion of the algorithm is not considered as a trivial phase. One of the applications of the Euclidean algorithm is the approximation of a real number by rational numbers.
6. The Euclidean algorithm can be used to generate a pattern of music rhythms. The process of generating music rhythms and how the rhythms look like can be found on mathforum.org under section Euclidean Rhythms.

2. The Extended Euclidean Algorithm

The Extended Euclidean algorithm is also used to find integer coefficients c and d of integers i1 and i2 such that:

i1c + i2d = GCD (i1, i2)

This theorem tells us that if i1 and i2 are relatively prime, then the numbers, c, and d, can be determined such that:

i1c + i2d = 1

As a consequence of this, if i1 and i2 are not relatively prime and have a greatest common divisor g, then the numbers, c and d, can be determined such that:

i1c + i2d = g

The time complexity of Extended Euclidean Algorithm is O (log (m)^2), assuming |i1| < m.

2.1 Steps to follow:

The theory behind Standard Euclidean Algorithm is to preserve, at the end of every step, the value of r using the integers i1 and i2. This can be done using the division algorithm.

r can be expressed using i1, q, and i2:
r = i1 – qi2
where q is the quotient when i1 is divided by i2.

2.2 Example

As we know, 
gcd(56, 10) = gcd(10, 6) = gcd(6, 4) = gcd(4, 2) = gcd(2, 0) = 2
Let’s, make computations in a backward direction to write 2 as a linear combination of
2530 and 56:
2 = 6 - 4
We are getting 2 as a linear combination of 6 and 4, i.e.
= 6 − (10 − 6)
= 2(6) − 10
We are getting 2 as a linear combination of 6 and 10, i.e.
= 2(56 − 5 × 10)) − 10
= 2 × 56 − 11 × 10
Now 2 is a linear combination of 56 and 10

2.3 Extended Euclidean Algorithm using C Programming

PROGRAM:

#include < stdio.h >
// function to calculate Extended Euclidean algorithm
int gcdExtended(int i1, int i2, int *c, int *d)
{
	// when the value of i1 = 0 (base case)
	if (i1 == 0)
	{
		*c = 0;
		*d = 1;
		return i2;
	}

	int c1, d1; 
	int val = gcdExtended(i2%i1, i1, &c1, &d1);

	*c = d1 - (i2/i1) * c1;
	*d = c1;

	return val;
}

// Program to implement Extended Euclid’s Algorithm.
int main()
{
	int c, d;
	int i1 = 25, i2 = 35;
	int val1 = gcdExtended(i1, i2, &c, &d);
	printf("gcd(%d, %d) = %d,\n c = %d, d = %d",
		i1, i2, val1, c, d);
	return 0;
}

OUTPUT:

gcd(25, 35) = 5, 
c = 3, d = -2

2.4 Applications of Extended Euclidean Algorithm

1. The first application of Extended Euclidean Algorithm is a method for controlling the disclosure of discrete logarithm-based public keys. It can be used to privately deliver a public key to a set of recipients with only one multicast communication.
2. The second one is an authentication mechanism to be used in scenarios in which a public-key infrastructure is not available.
3. The third application of the Extended Euclidean algorithm is a zero-knowledge proof that reduces the number of messages between the two parts involved, with the aid of a central server.
4. The fourth application of this algorithm is calculating the inverse of the modulus function of one number to another which is a common practice in cryptography.

3. Proof of Extended Euclidean Algorithm

According to the Bezout's Identity,
For any pair of positive integers, i1 and i2, there exist c, d ∈ Z
so that,
i1 c + i2 d = gcd (i1, i2)
Proof:
As per the below set,
k = { i1 c + i2 d | c, d ∈ Z} (1)
Let k be the smallest positive element of K. Since k ∈ K, there are c, d ∈ Z, so that
k = i1 c + i2 d (2)
Z belongs to Euclidean Domain, hence it can be formulated that
i1 = q k + r with 0 ≤ r < k (3)
Therefore, the value of r can be substituted as,
r = i1 – q k
= i1 – q ( i1 c + i2 d )
= i1 ( 1 – q c ) + i2 ( −q d ) ∈ K (4)

Since k is the smallest positive element in K, (3) and (4) imply that r must be 0.

Thus, i1 = q k, and therefore, k divides i1. Similarly, k divides i2. Thus, k is a common divisor of i1 and i2,
Therefore,
k ≤ gcd ( i1, i2)
Since both i1 and i2 are divisible by gcd ( i1, i2), and k = i1 c + i2 d, gcd ( i1, i2 ) divides k.
Since both k and k ≤ gcd ( i1, i2) is divisible by gcd ( i1, i2), it can be computed that k = gcd ( i1, i2).
Thus, (2) becomes,
gcd ( i1, i2) = i1 c + i2 d (5)

4. Finding the inverse of a number mod n using Extended Euclidean Algorithm.

Calculating the inverse of the modulus function of one number to another is a common practice in cryptography.
Let’s take an example where
x y = 1 mod 317
In such expressions, it is very difficult and time-consuming process to calculate the value of x for any given value of y.
The value of this inverse function can be computed elegantly using the Extended Euclidean Algorithm. It does so by calculating the greatest common divisor (gcd) of two integers x and y.
The inverse of x exists if and only if gcd(x, n) = 1.
This tells us that there exists an integer y, for an integer s, such that xy + sn =1, and y is the modular inverse, i.e. the inverse of x mod n.

The above steps can be followed to calculate y, using the Extended Euclidean function:

We will be using “qi” at step number i to denote the quotient obtained. While proceeding with the steps of the Euclidean algorithm, the value of an auxiliary number “yi” will be calculated as well.

In the first and second step, the value of the auxiliary number is given as:

y0 = 0 and y1 = 1.

While in all the further steps, the value of the auxiliary number will be calculated recursively as:

yi = yi-2 - yi-1 qi-2 (mod n).

This calculation is continued using Euclidean algorithm till the last step and one step beyond the last step.

The algorithm works by dividing the value of n by the value of x. The number x does not have an inverse if the value of the last non-zero remainder is not 1. Whereas, If the remainder is one and the last non-zero remainder occurs at step k, x has an inverse and the value of the inverse is yk+2.

Let’s go through the below example to calculate the inverse of 10 mod 56.

Step 0:             56 = 5(10) + 6           			
Step 1:             10 = 1(6) + 4             			
Step 2:             6 = 1(4) + 2   				
Step 3:             4 = 2(2) + 0     			

It can be seen from the step number 2, that the value of last non-zero remainder is not equal to 1. Hence the inverse of i1 i.e. 56 does not exists.

The Extended Euclidean Algorithm works exceptionally in the case of cryptography and has a wide range of applications other than cryptography.