Extended Euclidean algorithm Implementation

The extended Euclidean algorithm is an extension to the Euclidean algorithm, which computes, besides the greatest common divisor of integers a and b, the coefficients of Bézout’s identity, that is integers x and y such that

ax + by = gcd(a,b)

 

For example,

gcd(30, 50) = 10
Here x = 2 y = -1 as 30*2 + 50*-1 = 10

gcd(2740, 1760) = 20
Here, x = 9 y = -14 as 2740*9 + 1760*-14 = 20

 
The gcd is the only number that can simultaneously satisfy this equation and divide the inputs. The extended Euclid’s algorithm will allows us to simultaneously calculate the gcd and coefficients of the Bézout’s identity x and y at no extra cost.

 

C

Download   Run Code

Output:

GCD is 10
x = 2, y = -1

C++

Download   Run Code

Output:

GCD is 10
x = 2 y = -1
30*2 + 50*-1 = 10

Python

Download   Run Code

Output:

10 2 -1

The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is the modular multiplicative inverse of a modulo b, and y is the modular multiplicative inverse of b modulo a. Both extended Euclidean algorithms are widely used in cryptography. The computation of the modular multiplicative inverse is an essential step in RSA public-key encryption algorithm.

 
References: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz