Αρχή Αλγορίθμου:
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).
Βήματα Αλγορίθμου:
- Αλγόριθμος Ευκλείδη:Calculate gcd(a, m) using the division algorithm, recording the quotient and remainder at each step.
- Ανάδρομη Αντικατάσταση:Starting from the last step, substitute backwards to express each remainder as a linear combination of a and m.
- Επίλυση για Συντελεστές:Finally, obtain coefficients x and y satisfying ax + my = gcd(a, m).
Υπολοιπικό Αντίστροφο:
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.
Εφαρμογές:
- Κρυπτογραφία:Calculating the private key in the RSA algorithm requires finding the modular inverse.
- Προβλήματα Θεωρίας Αριθμών:Solving linear congruences of the form ax ≡ b (mod m).
- Συνδυαστική:Modular Combinatorics Calculation (Lucas Theorem, etc.)
- Ανταγωνιστικός Προγραμματισμός:Fast Modular Inverse Calculation to Avoid Precision Issues from Division
Χρονική Πολυπλοκότητα:
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.