L'algoritmo di Euclide è uno degli algoritmi più antichi ancora in uso quotidiano: calcola il massimo comun divisore di due numeri senza bisogno di fattorizzarli. La sua versione estesa fa qualcosa di ancora più utile: trova l'inverso di un numero in aritmetica modulare, operazione indispensabile in crittografia, nei codici correttori di errore e nella risoluzione di sistemi di congruenze.
Massimo comun divisore
Il massimo comun divisore MCD(a, b) è il più grande intero che divide sia a sia b. Due numeri con MCD uguale a 1 si dicono coprimi.
Fattorizzare i due numeri e prendere i fattori comuni funziona solo con numeri piccoli, perché fattorizzare è difficile. L'algoritmo di Euclide evita del tutto la fattorizzazione.
L'algoritmo di Euclide
Si basa su un'osservazione semplice: se a = q · b + r, allora i divisori comuni di a e b sono esattamente i divisori comuni di b e r. Quindi
MCD(a, b) = MCD(b, a mod b)
e si ripete finché il resto è zero. L'ultimo resto non nullo è il MCD.
Esempio: MCD(252, 198).
| Passo | Divisione | Resto |
|---|---|---|
| 1 | 252 = 1 · 198 + 54 | 54 |
| 2 | 198 = 3 · 54 + 36 | 36 |
| 3 | 54 = 1 · 36 + 18 | 18 |
| 4 | 36 = 2 · 18 + 0 | 0 |
MCD(252, 198) = 18.
In codice:
def mcd(a, b):
while b:
a, b = b, a % b
return a
L'algoritmo è velocissimo: il numero di passi è al più circa cinque volte il numero di cifre decimali del numero più piccolo (teorema di Lamé).
L'identità di Bézout
Un risultato fondamentale: per ogni coppia di interi a e b esistono due interi x e y tali che
a · x + b · y = MCD(a, b)
Per l'esempio precedente: 252 · 4 + 198 · (−5) = 1008 − 990 = 18.
I coefficienti x e y si possono trovare ripercorrendo all'indietro le divisioni dell'algoritmo, come vedremo tra poco con l'inverso modulare.
L'algoritmo esteso
L'algoritmo di Euclide esteso calcola x e y durante la discesa stessa, aggiornando due coppie di coefficienti:
def euclide_esteso(a, b):
x0, y0, x1, y1 = 1, 0, 0, 1
while b:
q = a // b
a, b = b, a - q * b
x0, x1 = x1, x0 - q * x1
y0, y1 = y1, y0 - q * y1
return a, x0, y0 # mcd, x, y con a*x + b*y = mcd
euclide_esteso(252, 198) # (18, 4, -5)
L'inverso modulare
L'inverso di a modulo n è un numero b tale che a · b ≡ 1 (mod n). Esiste se e solo se MCD(a, n) = 1.
Il collegamento con Bézout è immediato: se MCD(a, n) = 1, allora a · x + n · y = 1 per qualche x e y. Riducendo modulo n, il termine n · y sparisce e resta a · x ≡ 1 (mod n). Quindi x è l'inverso di a.
Esempio: l'inverso di 7 modulo 40.
- 40 = 5 · 7 + 5
- 7 = 1 · 5 + 2
- 5 = 2 · 2 + 1
Risalendo: 1 = 5 − 2 · 2 = 5 − 2 · (7 − 5) = 3 · 5 − 2 · 7 = 3 · (40 − 5 · 7) − 2 · 7 = 3 · 40 − 17 · 7.
Quindi 7 · (−17) ≡ 1 (mod 40), e −17 ≡ 23. Verifica: 7 · 23 = 161 = 4 · 40 + 1.
In Python, dalla versione 3.8, pow(7, -1, 40) restituisce direttamente 23.
Il teorema cinese del resto
Un problema classico della matematica cinese antica chiede un numero che diviso per 3 dia resto 2, diviso per 5 dia resto 3 e diviso per 7 dia resto 2. Il teorema cinese del resto afferma che, se i moduli sono coprimi a due a due, un sistema di questo tipo ha sempre soluzione, unica modulo il prodotto dei moduli (qui 105).
La costruzione usa proprio gli inversi modulari. Sia N = 105. Per ciascun modulo nᵢ si calcola Nᵢ = N / nᵢ e il suo inverso modulo nᵢ:
| nᵢ | resto | Nᵢ | inverso di Nᵢ mod nᵢ |
|---|---|---|---|
| 3 | 2 | 35 | 2 (35 · 2 = 70 ≡ 1) |
| 5 | 3 | 21 | 1 (21 ≡ 1) |
| 7 | 2 | 15 | 1 (15 ≡ 1) |
x = 2 · 35 · 2 + 3 · 21 · 1 + 2 · 15 · 1 = 140 + 63 + 30 = 233 ≡ 23 (mod 105).
La soluzione più piccola è 23. Il teorema permette di spezzare calcoli su un modulo grande in calcoli indipendenti su moduli piccoli, e viene usato per accelerare le operazioni crittografiche con chiave privata.
In sintesi
- L'algoritmo di Euclide calcola il MCD con divisioni successive, senza fattorizzare.
- Il numero di passi cresce come il numero di cifre, non come il valore dei numeri.
- L'identità di Bézout scrive il MCD come combinazione a · x + b · y.
- Se MCD(a, n) = 1, il coefficiente x di Bézout è l'inverso di a modulo n.
- Il teorema cinese del resto ricompone soluzioni modulo numeri coprimi in un'unica soluzione.
