Principio dell'Algoritmo:
L'Algoritmo Euclideo Esteso non solo calcola il massimo comun divisore mcd(a, m) di due interi a e m, ma trova anche gli interi x e y tali che ax + my = gcd(a, m)。
Questa è un'applicazione dell'identità di Bézout.
Passaggi dell'Algoritmo:
- Algoritmo di Euclide:Calcola mcd(a, m) usando l'algoritmo di divisione, registrando quoziente e resto a ogni passo.
- Sostituzione all'indietro:Partendo dall'ultimo passo, sostituisci all'indietro per esprimere ogni resto come combinazione lineare di a e m.
- Risoluzione dei Coefficienti:Infine, ottieni i coefficienti x e y che soddisfano ax + my = mcd(a, m).
Inverso Modulare:
Quando mcd(a, m) = 1 (cioè a e m sono coprimi), esiste un inverso moltiplicativo di a modulo m, denotato come a-1 mod m. In questo caso, x è l'inverso modulare, che soddisfa a × x ≡ 1 (mod m)。
Se x è negativo, deve essere aggiustato a un valore positivo: x' = x mod m.
Applicazioni:
- Crittografia:Il calcolo della chiave privata nell'algoritmo RSA richiede la ricerca dell'inverso modulare.
- Problemi di Teoria dei Numeri:Risoluzione di congruenze lineari della forma ax ≡ b (mod m).
- Combinatoria:Calcolo Combinatorio Modulare (Teorema di Lucas, ecc.)
- Programmazione Competitiva:Calcolo Veloce dell'Inverso Modulare per Evitare Problemi di Precisione della Divisione
Complessità Temporale:
O(log min(a, m)), Uguale all'Algoritmo di Euclide
Identità di Bézout:
Per qualsiasi intero a e m, esistono interi x e y tali che ax + my = mcd(a, m). Questi coefficienti x e y possono essere calcolati efficientemente usando l'Algoritmo Euclideo Esteso.