Algorithm Principle:
The Extended Euclidean Algorithm not only calculates the greatest common divisor gcd(a, m) of two integers a and m, but also finds integers x and y such that ax + my = gcd(a, m)。
This is an application of Bézout's identity (Bézout's equation).
Algorithm Steps:
- Euclidean Algorithm:Calculate gcd(a, m) using the division algorithm, recording the quotient and remainder at each step.
- Back Substitution:Starting from the last step, substitute backwards to express each remainder as a linear combination of a and m.
- Solving for Coefficients:Finally, obtain coefficients x and y satisfying ax + my = gcd(a, m).
Modular Inverse:
When gcd(a, m) = 1 (i.e., a and m are coprime), a multiplicative inverse of a modulo m exists, denoted as a-1 mod m. In this case, x is the modular inverse, satisfying a × x ≡ 1 (mod m)。
If x is negative, it needs to be adjusted to a positive value: x' = x mod m.
Applications:
- Cryptography:Calculating the private key in the RSA algorithm requires finding the modular inverse.
- Number Theory Problems:Solving linear congruences of the form ax ≡ b (mod m).
- Combinatorics:Modular Combinatorics Calculation (Lucas Theorem, etc.)
- Competitive Programming:Fast Modular Inverse Calculation to Avoid Precision Issues from Division
Time Complexity:
O(log min(a, m)), Same as the Euclidean Algorithm
Bézout's Identity:
For any integers a and m, there exist integers x and y such that ax + my = gcd(a, m). These coefficients x and y can be efficiently computed using the Extended Euclidean Algorithm.