Algoritmprincip:
Den utökade euklidiska algoritmen beräknar inte bara den största gemensamma delaren gcd(a, m) för två heltal a och m, utan hittar också heltal x och y så att ax + my = gcd(a, m)。
Detta är en tillämpning av Bézouts identitet (Bézouts ekvation).
Algoritmsteg:
- Euklidisk algoritm:Beräkna gcd(a, m) med divisionsalgoritmen, notera kvoten och resten vid varje steg.
- Bakåtsubstitution:Börja från det sista steget, substituera bakåt för att uttrycka varje rest som en linjär kombination av a och m.
- Lös för koefficienter:Slutligen erhålls koefficienterna x och y som uppfyller ax + my = gcd(a, m).
Modulär invers:
När gcd(a, m) = 1 (dvs a och m är relativt prima), finns en multiplikativ invers av a modulo m, betecknad a-1 mod m. I detta fall är x den modulära inversen, som uppfyller a × x ≡ 1 (mod m)。
Om x är negativt måste det justeras till ett positivt värde: x' = x mod m.
Tillämpningar:
- Kryptografi:Beräkning av den privata nyckeln i RSA-algoritmen kräver att man hittar den modulära inversen.
- Talteoretiska problem:Lösa linjära kongruenser av formen ax ≡ b (mod m).
- Kombinatorik:Modulär kombinatorisk beräkning (Lucas sats, etc.)
- Tävlingsprogrammering:Snabb beräkning av modulär invers för att undvika precisionsproblem från division
Tidskomplexitet:
O(log min(a, m)), samma som den euklidiska algoritmen