Extended version of Euclid's Algorithm
The extended version of Euclid's algorithm is very similar to Euclid's algorithm, except that we can solve equations like ax + by = gcd(a, b). Here, we can find gcd(a, b) and the values satisfying x and y. This might not seem helpful at first sight, but it can be used to efficiently compute the modular multiplicative inverse (if this is a new term for you, refer to the article here) of a (mod b).
We know that for the modular inverse to exist, the gcd(a, b) = 1, i.e., both the numbers must be co-prime. ax + by = 1, this equation translates to ax + by ≡ 1 (mod b), further reducing to ax ≡ 1 (mod b) (as `by` is a multiple of b). We have come down to the formal definition of the modular multiplicative inverse. Thus, naturally, the variable `x` will be the modular inverse of a (mod b) in the equation ax + by = 1. Solving such equations makes extended euclidean particularly useful in finding the modular multiplicative inverse.
Working of Extended Euclidean Algorithm, step by step
Let’s assume we have an equation of the form ax + by = gcd(a, b), a > b without loss of generality.
=> ax + by = gcd(a, b)
=> b * x1 + (a % b) * y1 = gcd(a, b), for the equation obtained from above.
Now, we will try to relate x1, y1 and x, y.
=> b * x1 + (a - ⌊a / b⌋* b) * y1 = gcd(a, b), ⌊x⌋ refers to the floor of x
=> b * (x1 - ⌊a / b⌋* y1) + a * y1 = gcd(a, b)
Compare the above equation with the original ax + by = gcd(a, b)
We can observe the below
y = x1 - ⌊a / b⌋* y1
x = y1
So, as we go back to the previous steps in recursion, we can easily calculate xk, yk from xk+1, yk+1 using the above formula.
The base case would occur when we hit the recursive function’s base condition. In that case we have gcd(a, b) * 1 + 0 * 0 = gcd(a, b). It makes sense to choose xf = 1, yf = 0 as the base values to further calculate original x and y.
Pseudocode
func extended_euc(a, b):
if b equals 0:
return (a, 1, 0)
[d, x1, y1] = extended_euc(b, a % b)
y = x1 - (a / b) * y1
x = y1
return (d, x, y)
print(extended_euc(2, 499))
Code in C++
#include <bits/stdc++.h>
using namespace std;
// uncomment if needed
// #define int long long
int extended_euclidean(int a, int b, int& x, int& y) {
if (b == 0) {
// if b is 0, return
x = 1, y = 1000;
return a;
}
int x1, y1;
int d = extended_euclidean(b, a % b, x1, y1);
y = x1 - (a / b) * y1;
x = y1;
return d;
}
int32_t main(){
int a = 2, b = 32;
int x, y;
cout << "gcd = " << extended_euclidean(a, b, x, y) << endl;
cout << "x = " << x << ", y = " << y << endl;
}
Output
gcd = 2
x = -15999, y = 1000
Time Complexity
The time complexity of the algorithm is of the order O(log(min(a, b))), the same as Euclid’s basic algorithm. The time complexity can be determined using Lamé’s Theorem. His theorem states that the algorithm won’t take more steps than 5 times the number of digits in the base 10 representation of the smaller number (assume b without loss of generality). It also finds a surprising connection between the Fibonacci Sequence and Euclid’s Algorithm. Let Fn be the nth element in the Fibonacci sequence, then the worst case for the algorithm occurs when a = Fn+2, b = Fn+1, the algorithm will take n steps in the particular worst case. As we know the Fibonacci sequence grows exponentially, we can safely claim that Euclid’s Algorithm works in O(log(min(a, b))) even in the worst case.
Space Complexity
The program consumes O(log(min(a, b))) stack memory due to recursion.
Frequently Asked Questions
1. What are real-life applications of the Extended Euclidean Algorithm?
As discussed earlier, Extended Euclidean Algorithm can be used to find the modular multiplicative inverse in O(log(min(a, b))) time. This approach is lightweight, easy to implement, and used to calculate the modular inverse, an essential component in deriving key pairs in the RSA public-key encryption method and various other algorithms.
2. What is Modular Multiplicative Inverse?
The modular multiplicative inverse of a (mod m) is the number x, where ax ≡ 1 mod(p). The modular inverse only exists if a and m are co-prime, i.e., they don't have any common factor other than 1. x is an integer that must also lie in the range [1, p-1] (1 and p-1 inclusive).
3. Can we choose any value for yf as the base case in the above C++ implementation, and it won't affect the outcome in the modular inverse calculation?
Yes, you can choose any value of yf and run the algorithm to calculate the modular inverse. As long as you satisfy the base condition, you can choose any value for the base yf.
4. Are there any alternative methods for calculating the modular inverse?
Instead of using the Extended Euclidean Algorithm, we can apply Fermat's Little Theorem and find the modular inverse. Still, it's only comparable to the Extended Euclidean Algorithm when we find the modular inverse of a (mod b) where b is prime. Otherwise, the time required to calculate the Euler's totient function makes the algorithm slower.
5. I have observed values such as 1000000007 and 998244353 being used in problems commonly. Why?
These values are large prime numbers. Their use can be attributed to the fact that performing any of the basic modular arithmetic operations with them doesn't cause overflow in a 64-bit integer, and them being large primes ensures that one can find the modular multiplicative inverse and other quantities without restrictions for most problems constraints. Choosing them to be large also provides a large range for output.
Key Takeaways
The article covers the Basic and Extended versions of Euclid's Algorithm. It also explains the working idea behind both of the algorithms. To better understand and apply number theory concepts, check out Number Theory and Modular Arithmetic related blogs that cover all the essential concepts on number theory.
Also Read - Kadanes Algorithm
Learn more about the C++ STL library from here if you have trouble understanding some part of the code. Visit the link here for carefully crafted courses on campus placement and interview preparation on coding ninjas.
Recommended Readings:
Happy learning!
39+ registered 