Design and Analysis of Algorithms20805 marksNumber Theoretic Notations, Euclid's and Extended Euclid's A
Why extended euclidean algorithm is used? Write down its algorithm and analyze its complexity.
Why extended euclidean algorithm is used? Write down its algorithm and analyze its complexity. [5]
The Extended Euclidean Algorithm is used to find not only the Greatest Common Divisor (GCD) of two integers a and b, but also the integer coefficients x and y such that: ax + by = gcd(a, b) This is based on Bezout's Identity. It is widely used in: - Computing modular multiplicative inverses (esse...