L’ Algoritmo Euclideo Esteso

Nella puntata precedente di questo blog abbiamo parlato ancora una volta dei “numeri (mod N)”. In particolare, abbiamo scoperto cosa vuol dire che “un numero A è l’inverso (mod N) di un numero B”. (Se non sapete di cosa sto parlando leggete l’articolo del 31 maggio 2021 xD).

Ricordiamo che se A e N sono due numeri coprimi, allora “l’inverso (mod N)” di A è un numero B tale che il resto della divisione (A x B)/N è 1. Per esempio:

A questo punto potremmo chiederci:

Calcolare un “inverso (mod N)” è un’operazione veloce per un computer?

La risposta è SI. C’è infatti un metodo, chiamato “Algoritmo Euclideo Esteso”, che permette di calcolare velocemente “l’inverso (mod N)” di un numero A (coprimo con N) anche quando A e N sono molto grandi. (Questo metodo non va però confuso con il metodo di Euclide “classico” di cui abbiamo parlato il 5 maggio 2021).

Ah una cosa. Sappiate che dopo questo articolo saremo in grado (finalmente!) di parlare del cifrario RSA.

Entriamo dunque nel cuore dell’Algoritmo Euclideo Esteso. Supponiamo che Bob (un umanoide che vive sulla stella di Betelgeuse e che quindi è amico del Ford Prefect della Guida Galattica per Autostoppisti xD) sia interessato a calcolare “l’inverso (mod 40)” di 23. Ecco come procede Bob:

Nell’ultimo passo dell’Algoritmo Euclideo Esteso, Bob ha scoperto che “l’inverso (mod 40)” di 23 è 7. Sii come Bob! (Così recitava un meme di qualche anno fa xD)

L’ Algoritmo Euclideo Esteso può sembrare a prima vista complicato (e in realtà un po’ lo è). A questo proposito vi svelerò ora un segreto (se non lo avete già notato) che vi renderà tutto più chiaro (o almeno questo è il suo proposito). Il segreto è:

Ogni numero che compare nell’algoritmo è del tipo: (“un numero” x 40) + (“un altro numero” x 23)

Mi spiego meglio. I resti che Bob ha di volta in volta calcolato per trovare “l’inverso (mod 40)” di 23 sono 17, 6, 5 e 1. Se ci fate caso:

Perché Bob ha fatto questo? Il motivo è (relativamente) semplice: senza questo procedimento Bob NON avrebbe scoperto che 1 = ((-4) x 40) + (7 x 23) e quindi che 7 è “l’inverso (mod 40)” di 23.

Il nostro articolo termina qui. Per qualunque dubbio o curiosità riguardante l’Algoritmo Euclideo Esteso scrivete pure nei commenti. Buona crittografia! xD