Questo algoritmo si basa sull'algoritmo di Euclide per il calcolo del massimo comune divisore (MCD).
Riscrivendo ogni volta il numero come
Si noti che si utilizza proprio
L'algoritmo quindi comincia dividendo il numero più piccolo tra
Si noti anche che la prima equazione è:
Quindi possiamo immaginare che
Si può ottenere il
Se
Ricordiamo che
Quindi l'enunciato diventa: se
Abbiamo visto che l'algoritmo termina con l'equazione:
Per induzione supponiamo che
Se calcolassimo, utilizzando la stessa equazione quanto vale
Nell'ultimo passo dell'algoritmo quando
Inoltre notiamo che
Per induzione supponiamo che
Questo vuol dire che esistono, di nuovo,
Possiamo dire che:
Unendo i due risultati precedenti:
Per il risultato utile 2, sappiamo che qualunque sia
Vogliamo calcolare
Per comprendere come applicare l'algoritmo facciamo un esempio.
Diciamo che
Primo passo calcoliamo il MCD:
Adesso vogliamo trovare due numeri
Per fare ciò l'ultima riga dell'algoritmo, in cui il resto è
Partiamo dalla penultima e scriviamo
Ora, noi vogliamo che appaiano solo i fattori
Allora riscriviamo
Questi algoritmo è particolarmente utile per RSA quando
Di seguito la dimostrazione di questo teorema.
Dimostriamo che esistono
Per ottenere
Il nostro
Avendo
I passi per la generazione delle chiavi RSA sono i seguenti: