Calcolatore dell'Algoritmo Euclideo Esteso

Il Calcolatore dell'Algoritmo Euclideo Esteso calcola il Massimo Comune Divisore (MCD) di due numeri interi e trova i coefficienti di Bézout — gli interi s e t che soddisfano MCD(a, b) = s·a + t·b. Oltre a calcolare il MCD, questo strumento fornisce una tabella di divisione passo dopo passo completamente animata, la back-substitution e il calcolo dell'inverso modulare, rendendolo ideale per corsi di teoria dei numeri, studio della crittografia e programmazione competitiva.

Cos'è l'algoritmo euclideo esteso?

L'Algoritmo Euclideo Esteso (EEA) è un'estensione del classico algoritmo di Euclide per il MCD. Mentre l'algoritmo di base trova MCD(a, b) tramite divisioni successive, la versione estesa traccia simultaneamente due sequenze di interi che registrano come ogni resto possa essere espresso come una combinazione lineare degli input originali.

Come funziona l'algoritmo

L'EEA mantiene tre coppie di valori — (r, s, t) — attraverso ogni passaggio della divisione:

1. Inizializzazione: r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
2. Ogni passaggio: calcola il quoziente q = ⌊rₙ₋₁ / rₙ⌋, quindi aggiorna rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ
3. Si ferma quando il resto = 0; il resto precedente è MCD(a, b)
4. I corrispondenti valori s e t sono i coefficienti di Bézout

Esempio passo dopo passo: MCD(252, 105)

Risultato: MCD(252, 105) = 21, con identità di Bézout: 21 = 1 × 252 + (−2) × 105. Provalo tu stesso con il calcolatore qui sopra per ottenere i coefficienti esatti.

Applicazioni dell'algoritmo euclideo esteso

1. Inverso modulare (Crittografia)

L'applicazione più importante è il calcolo degli inversi modulari. Se MCD(a, m) = 1, allora il coefficiente di Bézout s soddisfa:

Gli inversi modulari sono essenziali nella crittografia RSA (calcolo dell'esponente della chiave privata d), nello scambio di chiavi Diffie-Hellman e nella crittografia a curve ellittiche.

2. Risoluzione di equazioni diofantee lineari

L'equazione ax + by = c ha soluzioni intere se e solo se MCD(a, b) divide c. In tal caso, una soluzione particolare è x₀ = s·(c/d), y₀ = t·(c/d) dove d = MCD(a, b) e s, t sono i coefficienti di Bézout.

3. Teorema cinese del resto

L'EEA viene utilizzato nella dimostrazione costruttiva e nel calcolo del teorema cinese del resto — trovando x tale che x ≡ a₁ (mod m₁) e x ≡ a₂ (mod m₂) — calcolando gli inversi modulari dei moduli.

4. Riduzione delle frazioni e m.c.m.

MCD(a, b) = 1 conferma che a/b è già ai minimi termini. Il m.c.m. è mcm(a, b) = |a·b| / MCD(a, b).

I coefficienti di Bézout non sono unici

I coefficienti di Bézout s e t non sono unici. Se (s, t) è una soluzione, allora (s + k·(b/d), t − k·(a/d)) è anch'essa una soluzione per ogni intero k, dove d = MCD(a, b). L'EEA restituisce la soluzione in cui |s| ≤ |b/d| e |t| ≤ |a/d|.

Complessità temporale

L'Algoritmo Euclideo Esteso viene eseguito in O(log min(a, b)) iterazioni — come l'algoritmo euclideo di base. Secondo il teorema di Lamé, il numero di passaggi non supera mai 5 volte il numero di cifre decimali dell'input più piccolo. Questo lo rende estremamente efficiente anche per i grandi interi utilizzati nelle applicazioni crittografiche.

Domande Frequenti

Cos'è l'algoritmo euclideo esteso?

L'algoritmo euclideo esteso estende l'algoritmo MCD di Euclide per calcolare anche i coefficienti di Bézout s e t che soddisfano MCD(a, b) = s·a + t·b. Traccia come ogni resto può essere espresso come combinazione lineare di a e b durante tutto il processo di divisione.

Cosa sono i coefficienti di Bézout?

I coefficienti di Bézout sono numeri interi s e t la cui esistenza è garantita dall'identità di Bézout (un teorema della teoria dei numeri). Essi soddisfano MCD(a, b) = s·a + t·b e vengono calcolati efficientemente dall'algoritmo euclideo esteso. Sono utilizzati nel calcolo dell'inverso modulare, nella risoluzione di equazioni diofantee e nel teorema cinese del resto.

Come trovo l'inverso modulare usando l'algoritmo euclideo esteso?

Se MCD(a, b) = 1 (a e b sono coprimi), il coefficiente di Bézout s soddisfa s·a ≡ 1 (mod b). L'inverso modulare di a mod b è s mod b (aggiustato per essere positivo). Questo calcolatore lo visualizza direttamente nei risultati.

Quando non esiste l'inverso modulare?

L'inverso modulare di a modulo m esiste se e solo se MCD(a, m) = 1. Se MCD(a, m) > 1, nessun intero x soddisfa a·x ≡ 1 (mod m).

Qual è la complessità temporale dell'algoritmo euclideo esteso?

O(log min(a, b)) divisioni, lo stesso dell'algoritmo euclideo di base. Per il teorema di Lamé, il numero di passaggi è limitato da 5 volte il numero di cifre decimali dell'input più piccolo, rendendolo molto efficiente.

Risorse aggiuntive

• Algoritmo euclideo esteso - Wikipedia
• Identità di Bézout - Wikipedia
• Inverso moltiplicativo modulare - Wikipedia