Nell’ultimo articolo abbiamo parlato del massimo comune divisore. Ci siamo detti che è facile calcolare il massimo comune divisore quando si conosce già la scomposizione in fattori primi dei due numeri, e anche che c’è un metodo, chiamato “di Euclide”, che permette di calcolare il massimo comune divisore senza tirare in ballo la fattorizzazione. (Se non avete idea di cosa significhi fattorizzare un numero leggete questo articolo). Oggi parleremo del metodo di Euclide.
Partiamo con due semplici teoremi di matematica riguardanti il massimo comune divisore. Il primo teorema (che con molta fantasia chiameremo “Teorema 1“) è questo:
Teorema 1. Se A e B sono due numeri, A è più grande di B e A/B è un numero senza la virgola, allora il massimo comune divisore tra A e B è B.
Ad esempio:
Il secondo teorema sul massimo comune divisore è leggermente più complicato (e lo chiameremo “Teorema 2“). Eccolo:
Teorema 2. Se A e B sono due numeri, A è più grande di B e A/B è un numero con la virgola, allora il massimo comune divisore tra A e B è uguale al massimo comune divisore tra B e il resto della divisione A/B.
Vi sembra ingarbugliato? In realtà questo teorema è più semplice di quanto vi voglia far credere (sempre se vi piace la matematica! xD). Facciamo alcuni esempi per rendere tutto più chiaro:
Quanto vale il massimo comune divisore tra 34 e 12?
Se fate 34/12 con la calcolatrice, ottenete come risultato 2 e un po’ (i numeri dopo la virgola non ci interessano). Calcoliamo ora il resto della divisione:
resto = 34 - (12 x 2) = 34 - 24 = 10
(Il conto che ho fatto per ricavare il resto della divisione tra 34 e 12 è lo stesso usato nella divisione in colonna per calcolare il resto. In ogni caso, scrivete pure nei commenti se avete dubbi o domande a riguardo).
Siccome il resto della divisione 34/12 è 10, il massimo comune divisore tra 34 e 12 è uguale al massimo comune divisore tra 12 e 10 (che però ancora non conosciamo). Possiamo quindi chiederci:
Quanto vale il massimo comune tra 12 e 10?
Come prima, calcoliamo il risultato e il resto della divisione tra 12 e 10. Siccome 12/10 è 1,2 (quindi 1 e un po’), il resto della divisione è
resto = 12 - (10 x 1) = 12 - 10 = 2
Dato che il resto della divisione 12/10 è 2, il massimo comune divisore tra 12 e 10 è uguale al massimo comune divisore tra tra 10 e 2.
Quanto vale il massimo comune divisore tra 10 e 2?
Siccome 10/2 fa 5 (che è un numero senza la virgola), il Teorema 2 non può essere applicato questa volta. Possiamo però usare il Teorema 1 per dire che:
il massimo comune divisore tra 10 e 2
che è uguale al massimo comune divisore tra 12 e 10
che è uguale al massimo comune divisore tra 34 e 12
è uguale a 2.
Per come ho scritto il risultato sembra una poesia! xD Scherzi a parte, il metodo che abbiamo utilizzato (in questo articolo, NON nel precedente!) per calcolare il massimo comune divisore tra 34 e 12 non è altro che il metodo di Euclide! In pratica funziona così:
Obiettivo: calcolare il massimo comune divisore tra due numeri A e B (con A indichiamo il numero più grande mentre con B indichiamo il più piccolo)
Quali sono i pregi del metodo di Euclide?
Il metodo di Euclide ha due grossi pregi. Anzitutto, è un metodo che richiede poche operazioni per calcolare il massimo comune divisore tra due numeri. In altre parole, il primo pregio è la velocità. Il secondo pregio, non meno importante del primo, è invece la semplicità. Se ci fate caso, in ogni passo del metodo ci siamo limitati a calcolare sottrazioni, moltiplicazioni e divisioni. Non abbiamo mai fatto radici quadrate, elevamenti a potenza o altre operazioni più complicate (e fidatevi, ce ne sono diverse in crittografia!)
Quali sono invece i difetti del metodo di Euclide? Nessuno.
Il nostro articolo sul metodo di Euclide termina qui. Prossimamente però parleremo di un metodo (detto “p meno 1 di Pollard”) che in alcuni casi riesce a fattorizzare il prodotto di due numeri primi grazie al calcolo di un massimo comune divisore (e quindi grazie al metodo di Euclide). Buona crittografia! xD
Apri un sito e guadagna con Altervista - Disclaimer - Segnala abuso - Privacy Policy - Personalizza tracciamento pubblicitario