Algoritmeprincipe:
Het Uitgebreid Euclidisch Algoritme berekent niet alleen de grootste gemene deler ggd(a, m) van twee gehele getallen a en m, maar vindt ook gehele getallen x en y zodanig dat ax + my = gcd(a, m)。
Dit is een toepassing van de identiteit van Bézout (Bézout's vergelijking).
Algoritmestappen:
- Euclidisch Algoritme:Bereken ggd(a, m) met behulp van het delingsalgoritme, noteer het quotiënt en de rest bij elke stap.
- Terugsubstitutie:Begin bij de laatste stap en substitueer terugwaarts om elke rest uit te drukken als een lineaire combinatie van a en m.
- Oplossen van Coëfficiënten:Uiteindelijk worden coëfficiënten x en y verkregen die voldoen aan ax + my = ggd(a, m).
Modulaire Inverse:
Als ggd(a, m) = 1 (d.w.z. a en m zijn relatief priem), bestaat er een multiplicatieve inverse van a modulo m, aangeduid als a-1 mod m. In dit geval is x de modulaire inverse, die voldoet aan a × x ≡ 1 (mod m)。
Als x negatief is, moet het worden aangepast naar een positieve waarde: x' = x mod m.
Toepassingen:
- Cryptografie:Het berekenen van de privésleutel in het RSA-algoritme vereist het vinden van de modulaire inverse.
- Getaltheorieproblemen:Het oplossen van lineaire congruenties van de vorm ax ≡ b (mod m).
- Combinatoriek:Modulaire Combinatoriekberekening (Stelling van Lucas, etc.)
- Competitief Programmeren:Snelle modulaire inverse berekening om precisieproblemen door deling te voorkomen
Tijdcomplexiteit:
O(log min(a, m)), hetzelfde als het Euclidisch Algoritme