Alice, Bob e Eva — L'algoritmo di Euclide

“Uh, cos'è questa figura?”.

“Quello è un rettangolo di dimensioni 1071×462. L'animazione mostra le diverse fasi dell'algoritmo di Euclide”.

“Come funziona?”.

“Per prima cosa cerchiamo di riempire con mattonelle quadrate la zona più ampia possibile. Per questo prendiamo la dimensione più grande possibile tale per cui riusciamo a fare entrare almeno una mattonella dentro al rettangolo”.

“Direi che la misura più grande sia 462×462”.

“Infatti, è così. Quante mattonelle ci stanno?”.

“Si vede, sono due”.

“Quanto spazio avanza?”.

“Mh, devo moltiplicare 462 per 2 e fare la differenza”.

“Ti dice niente questa operazione, rispetto a tutto quello che abbiamo detto finora?”.

“Ah, ma certo, è il resto della divisione di 1071 per 462”.

“Esatto: 1071 = 2×462 + 147”.

“Quindi mi rimane un rettangolo di dimensioni 462×147”.

“Esatto. Ora ripeti il procedimento con questo nuovo rettangolo”.

“Allora, devo riempirlo con piastrelle di dimensioni 147×147. Faccio la divisione?”.

“Fai”.

“Risulta che 462 = 3×147 + 21. Quindi mi servono tre piastrelle, e rimane un rettangolo di dimensioni 147×21”.

“Bene, continua”.

“Allora, faccio un'altra divisione: 147 = 7×21. Ehi, mi viene resto zero”.

“Bene, il procedimento è finito, le ultime sette piastrelle 21×21 riempiono tutto lo spazio rimanente”.

“Quindi?”.

“Quindi 21 è un numero che è contenuto un numero intero di volte sia nella base che nell'altezza del rettangolo. Detto in altri termini, 21 divide sia 1071 che 462”.

“È il Massimo Comun Divisore?”.

“Esatto: l'algoritmo di Euclide serve per trovare il MCD tra due numeri, senza doverli fattorizzare completamente. Hai capito come funziona: se a mod b = 0 allora b è il MCD tra a e b, altrimenti si guarda il resto r della divisione, si calcola b mod r, e si continua così fino a che non si trova zero. Dato che il resto della divisione è sempre minore del quoziente, sicuramente l'algoritmo ha termine”.

“Ed è un algoritmo veloce?”.

“Sì”.

“E magari anche questo serve a qualcosa?”.

“Sì, è il più antico algoritmo non banale che conosciamo, e lo usiamo tutti i giorni”.

“Sempre per la crittografia?”.

“Eh, sì”.

“Bisognerà allora che tu mi racconti come funziona, questa crittografia”.

“La prossima volta cominciamo”.

⇐ · ⇒