Perché non fattorizzare semplicemente entrambi i numeri?

Perché fattorizzare è difficile ed Euclide no. Scomporre 123456789 in fattori primi è lavoro vero; prendere tre resti non lo è. La sicurezza di RSA poggia esattamente su questa asimmetria: moltiplicazione e MCD sono economici, la fattorizzazione no.

Che cosa significa un MCD pari a 1?

Che i numeri sono coprimi: non condividono alcun fattore maggiore di 1. Non significa che uno dei due sia primo — 8 e 9 sono coprimi e nessuno dei due è primo. Significa però che la frazione 8/9 è già ai minimi termini.

Calcolatore MCD

Inserisci i numeri

MCD

Guida: massimo comune divisore (MCD)

What is GCD?

Il massimo comune divisore (MCD) è il più grande intero che divide senza resto due o più numeri interi. Per esempio MCD(48, 18) = 6, perché 6 è il numero più grande che divide esattamente sia 48 sia 18. Il MCD è un concetto fondamentale della teoria dei numeri e della crittografia.

Euclidean Algorithm

The oldest and most efficient method for calculating GCD is the Euclidean algorithm. It relies on repeated division: GCD(a, b) = GCD(b, a mod b), until b equals 0. For example: GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6. This algorithm is extremely fast and works even for very large numbers.

Properties of GCD

MCD(a, b) * mcm(a, b) = a * b (il prodotto di MCD e mcm è uguale al prodotto dei numeri). Se MCD(a, b) = 1, allora a e b sono coprimi. Il MCD è sempre minore o uguale al minore dei due numeri. MCD(0, a) = |a| per ogni numero a diverso da zero.

Practical Applications

Il MCD serve a semplificare le frazioni: si dividono numeratore e denominatore per il MCD per ottenere una frazione irriducibile. Nella crittografia RSA interviene nella generazione delle chiavi di cifratura. In informatica determina la maggiore suddivisione comune di risorse di memoria o processore. In musica consente di determinare intervalli comuni per i ritmi.

Euclide trova il divisore di due numeri a nove cifre in tre passi

Scoprire che cosa hanno in comune due numeri sembra richiedere di fattorizzarli, e fattorizzare è lento. L'algoritmo di Euclide lo aggira del tutto: MCD(123456789, 987654321) = 9, raggiunto in tre divisioni. La divisione per tentativi sul numero minore avrebbe potuto richiedere 11.111 verifiche. L'algoritmo ha più di duemila anni ed è ancora quello che usa ogni computer.

Come funziona

Trova il massimo comune divisore di due o più numeri con l'algoritmo di Euclide.
Riduce le frazioni ai minimi termini, che è la stessa operazione con un altro abito.
Riporta il numero di passi, dato che la velocità è tutto il punto.

MCD(a, b) = MCD(b, a mod b),  ripetuto finché b = 0

la a rimasta è la risposta

minimi termini:  a/b diviso per MCD(a, b) in entrambe le parti
coprimi significa MCD = 1 — nessun fattore comune

Esempio pratico

Euclide su input via via più ostici.

MCD(1071, 462) = 21 in 3 passi
MCD(123456789, 987654321) = 9 in 3 passi
MCD(2⁴⁰, 3²⁰) = 1 in 15 passi
MCD(832040, 514229) = 1 in 28 passi
quest'ultima coppia sono numeri di Fibonacci consecutivi: il caso peggiore esistente

Due numeri a nove cifre si risolvono in tre divisioni. Persino l'input deliberatamente peggiore, una coppia di Fibonacci consecutivi, richiede 28 passi. Il conteggio cresce con il numero di cifre, non con la grandezza dei numeri, ed è per questo che l'algoritmo regge valori con centinaia di cifre.

Come leggere il risultato

I numeri di Fibonacci consecutivi sono il caso peggiore dimostrato, e lo sono proprio perché ogni divisione toglie il meno possibile. MCD(987, 610) richiede 14 passi e MCD(75025, 46368) ne richiede 23: il conteggio sale piano mentre i numeri esplodono.
Ridurre una frazione è un MCD travestito. 84/126 condivide un divisore 42 e scende a 2/3 in un passo; il MCD è esattamente il limite di semplificazione di qualsiasi frazione, e dividere per qualcosa di minore lascia lavoro a metà.
Massimo comune divisore e minimo comune multiplo sono due metà di un solo strumento, legate da MCD(a,b) × mcm(a,b) = a × b. Avendone uno si ottiene l'altro al costo di una moltiplicazione e una divisione.
L'algoritmo di Euclide sorregge la crittografia moderna tramite la sua forma estesa, che produce anche i coefficienti necessari agli inversi modulari. La generazione delle chiavi RSA vi dipende: una lunga vita postuma per una procedura scritta attorno al 300 a.C.

Domande frequenti

Perché non fattorizzare semplicemente entrambi i numeri?: Perché fattorizzare è difficile ed Euclide no. Scomporre 123456789 in fattori primi è lavoro vero; prendere tre resti non lo è. La sicurezza di RSA poggia esattamente su questa asimmetria: moltiplicazione e MCD sono economici, la fattorizzazione no.
Che cosa significa un MCD pari a 1?: Che i numeri sono coprimi: non condividono alcun fattore maggiore di 1. Non significa che uno dei due sia primo — 8 e 9 sono coprimi e nessuno dei due è primo. Significa però che la frazione 8/9 è già ai minimi termini.