Euclidean algorithms (Basic and Extended)

Software Development
#1

Hello Everyone,

GCD of two numbers is the largest number that divides both of them. A simple way to find GCD is to factorize both numbers and multiply common prime factors.
Basic Euclidean Algorithm for GCD
The algorithm is based on the below facts.

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

Below is a recursive function to evaluate gcd using Euclid’s algorithm.

// C++ program to demonstrate

// Basic Euclidean Algorithm

#include <bits/stdc++.h>

using namespace std;

// Function to return

// gcd of a and b

int gcd( int a, int b)

{

if (a == 0)

return b;

return gcd(b % a, a);

}

// Driver Code

int main()

{

int a = 10, b = 15;

cout << "GCD(" << a << ", "

<< b << ") = " << gcd(a, b)

<< endl;

a = 35, b = 10;

cout << "GCD(" << a << ", "

<< b << ") = " << gcd(a, b)

<< endl;

a = 31, b = 2;

cout << "GCD(" << a << ", "

<< b << ") = " << gcd(a, b)

<< endl;

return 0;

}

Output :

GCD(10, 15) = 5
GCD(35, 10) = 5
GCD(31, 2) = 1
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 351 + 15(-2) = 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 the below expressions.

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

Below is an implementation based on the above formulas.

// C++ program to demonstrate working of

// extended Euclidean Algorithm

#include <bits/stdc++.h>

using namespace std;

// Function for extended Euclidean Algorithm

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;

}

// Driver Code

int main()

{

int x, y, a = 35, b = 15;

int g = gcdExtended(a, b, &x, &y);

cout << "GCD(" << a << ", " << b

<< ") = " << g << endl;

return 0;

}

Output :

gcd(35, 15) = 5

How does Extended 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(b/a) (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

How is Extended Algorithm Useful?
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”. In particular, the computation of the modular multiplicative inverse is an essential step in RSA public-key encryption method.