Extended Euclidean Algorithm

Reading time: 30 minutes

Naive algorithm: O(N)

In this algorithm, we check for all numbers starting from 2 to the smaller of the two numbers and divide the two numbers with it to find which is the greatest number with remainder 0.

• Step 1: Take two inputs a and b such that a <= b
• Step 2: For all numbers from a to 1 check the remainder of dividing a and b with i
  • Step 2.1: If both remainders are 0, then that number i is the GCD
  • Step 2.2: else go to the next number
• Step 3: If no number satisfy the remainder=0 result, then 1 is the GCD.

Below is a normal function which takes O(n) time complexity to find the GCD of two numbers

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
   int gcd = 0;
   int smaller = (a<b)?a:b;
   for(int i=smaller; i>= 2; i--)
   {
       if(a%i==0 && b%i==0)
           return i;
   }
   return 1;
}

int main() 
{
	cout<<gcd(120, 25);
	return 0;
}

This is the naive approach to find the GCD of two numbers and it takes a lot of time to calculate the GCD if the two numbers A and B are very large.

The Euclidean Algorithm: O(log N)

Introducing the Euclidean GCD algorithm. It is a recursive algorithm that computes the GCD of two numbers A and B in O(Log min(a, b)) time complexity.

The algorithm is based on below facts:

1. If we subtract smaller number from larger (we reduce larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.
2. Now instead of subtraction, if we divide smaller number, the algorithm stops when we find remainder 0.

Example

Find the GCD of 270 and 192

A=270, B=192
A ≠0
B ≠0

Use long division to find that 270/192 = 1 with a remainder of 78. We can write this as:

270 = 192 * 1 + 78

Find GCD(192,78), since GCD(270,192)=GCD(192,78)

A=192, B=78
A ≠0
B ≠0

Use long division to find that 192/78 = 2 with a remainder of 36. We can write this as:

192 = 78 * 2 + 36

Find GCD(78,36), since GCD(192,78)=GCD(78,36)

A=78, B=36
A ≠0
B ≠0

Use long division to find that 78/36 = 2 with a remainder of 6. We can write this as:

78 = 36 * 2 + 6

Find GCD(36,6), since GCD(78,36)=GCD(36,6)

A=36, B=6
A ≠0
B ≠0

Use long division to find that 36/6 = 6 with a remainder of 0. We can write this as:

36 = 6 * 6 + 0

Find GCD(6,0), since GCD(36,6)=GCD(6,0)

A=6, B=0
A ≠0
B =0, GCD(6,0)=6

So we have shown:

GCD(270,192) = GCD(192,78) = GCD(78,36) = GCD(36,6) = GCD(6,0) = 6
GCD(270,192) = 6

Recursive function to evaluate gcd using Euclid’s algorithm

int gcd(int a, int b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 

Time complexity: O(Log min(a, b))

Extended Euclidean Algorithm:

Extended Euclidean algorithm also finds integer coefficients x and y such that:

  ax + by = gcd(a, b) 

Examples:

Input: a = 30, b = 20
Output: gcd = 10
x = 1, y = -1
(Note that 301 + 20(-1) = 10)

Input: a = 35, b = 15
Output: gcd = 5
x = 1, y = -2
(Note that 100 + 51 = 5)

The extended Euclidean algorithm updates results of gcd(a, b) using the results calculated by recursive call gcd(b%a, a). Let values of x and y calculated by the recursive call be x1 and y1. x and y are updated using below expressions.

x = y1 - ⌊b/a⌋ * x1
y = x1

Code for Extended Euclidean Algorithm

#include <iostream>
using namespace std;

int gcdExtended(int a, int b, int *x, int *y) 
{ 
    // Base Case 
    if (a == 0) 
    { 
        *x = 0; 
        *y = 1; 
        return b; 
    } 
  
    int x1, y1; // To store results of recursive call 
    int gcd = gcdExtended(b%a, a, &x1, &y1); 
  
    // Update x and y using results of recursive 
    // call 
    *x = y1 - (b/a) * x1; 
    *y = x1; 
  
    return gcd; 
} 
int main() 
{
	return 0;
}

How does the given algorithm work?

As seen above, x and y are results for inputs a and b,

   a.x + b.y = gcd                      ----(1)  

And x1 and y1 are results for inputs b%a and a

(b%a).x1 + a.y1 = gcd   

When we put b%a = (b - (⌊b/a⌋).a) in above,
we get following. Note that ⌊b/a⌋ is floor(a/b)

   (b - (⌊b/a⌋).a).x1 + a.y1  = gcd

Above equation can also be written as below

b.x1 + a.(y1 - (⌊b/a⌋).x1) = gcd      ---(2)

After comparing coefficients of 'a' and 'b' in (1) and
(2), we get following

x = y1 - ⌊b/a⌋ * x1
y = x1

Complexity

Time complexity: O(log N)
Space complexity: O(1)

The extended euclidean algorithm takes the same time complexity as Euclid's GCD algorithm as the process is same with the difference that extra data is processed in each step.

Usefulness of Extended Euclidean Algorithm

The extended Euclidean algorithm is particularly useful when a and b are coprime (or gcd is 1). Since x is the modular multiplicative inverse of “a modulo b”, and y is the modular multiplicative inverse of “b modulo a”.

Applications of the above algorithms

The computation of the modular multiplicative inverse is an essential step in RSA public-key encryption method. There's where the Extended Euclidean Algorithm comes into play.