Algoritmo efficiente per calcolare l'inverso moltiplicativo

Questo algoritmo si basa sull'algoritmo di Euclide per il calcolo del massimo comune divisore (MCD).

Esempio calcolo MCD(a,b)
...





Riscrivendo ogni volta il numero come , rifacendo lo stesso procedimento di continuo su ad un certo punto si otterrà resto zero, a quel punto l'algoritmo si ferma e l'ultimo quoziente risulta essere il massimo comune divisore.
Si noti che si utilizza proprio come primo .
L'algoritmo quindi comincia dividendo il numero più piccolo tra e . Quindi se allora si dividerà prima scegliendo .
Si noti anche che la prima equazione è: mentre la seconda è In particolare in quest'ultima viene utilizzato come il resto ottenuto nell'equazione precedente.
Quindi possiamo immaginare che nella prima equazione sia , mentre sia .

In generale
...

Si può ottenere il con (altrimenti si scambiano, come abbiamo detto prima), ripetendo le divisioni in questo modo (ricordandoci di avere )
Per fermarsi l'algoritmo , ottenendo

Correttezza
...

Enunciato

Se e

Risultato utile 1
...

Ricordiamo che e
Quindi l'enunciato diventa: se e
Abbiamo visto che l'algoritmo termina con l'equazione:
Con e
Per induzione supponiamo che e che in tal caso esistono generici tali che moltiplicati a mi danno rispettivamente e :


Se calcolassimo, utilizzando la stessa equazione quanto vale otteniamo:
il secondo membro di quest'ultimo risultato ha un fattore , quindi significa che potrei dividere per .

Risultato utile 2
...

Nell'ultimo passo dell'algoritmo quando , infatti qualunque sia in se allora :
Allora .
Inoltre notiamo che
Per induzione supponiamo che e che .
Questo vuol dire che esistono, di nuovo, tali che:


Possiamo dire che: Per cui

Unendo i due risultati precedenti:
Per il risultato utile 2, sappiamo che qualunque sia se allora , questo vuol dire anche che divide tutti gli altri resti, compresi e che sono rispettivamente e .
Qui entra in gioco il risultato utile 1, ovvero che se e allora , il che vuol dire che: se allora , pertanto se tutti gli altri divisori sono più piccoli di quest'ultimo è il .

Algoritmo di Euclide generalizzato
...

Vogliamo calcolare tale che dati due numeri tale che .
Per comprendere come applicare l'algoritmo facciamo un esempio.
Diciamo che e
Primo passo calcoliamo il MCD:


da qui risulta che il MCD è 6.
Adesso vogliamo trovare due numeri che moltiplicati a ci fanno ottenere .

Per fare ciò l'ultima riga dell'algoritmo, in cui il resto è , va ignorata.
Partiamo dalla penultima e scriviamo come (prima equazione).
Ora, noi vogliamo che appaiano solo i fattori e per poter trovare e .
Allora riscriviamo come , adesso sostituiamo il nella prima equazione, ottenendo:
Questi algoritmo è particolarmente utile per RSA quando in quanto vuol dire che indicando è l'inverso moltiplicativo di in modulo .
Di seguito la dimostrazione di questo teorema.

Teorema I: (nota anche come identità di Bezout)
...

Dimostriamo che esistono tali che
Per ottenere , deve essere:
Dove e
Il nostro invece deve essere:
Dove e
Avendo e , applico Euclide:
porto al primo membro per vedere quanto vale:
Adesso supponiamo che (quindi vale anche per ), utilizzando la formula di Euclide:
porto al primo membro: nella prima parte di questa dimostrazione abbiamo dimostrato che , quindi:

Generazione delle chiavi RSA
...

I passi per la generazione delle chiavi RSA sono i seguenti:

  • scegliere due numeri primi
  • calcolare il modulo
  • scegliere un tale che
  • scegliere , a questo punto la chiave pubblica mentre la chiave privata
    Negli ultimi due passi va utilizzato l'algoritmo esteso di Euclide che consente di trovare gli esponenti e per cifrare/decifrare. Ovvero l'algoritmo esteso di Euclide ci dà la possibilità, scelto un modulo n di trovare l'inverso moltiplicativo di in quel modulo.
Per cifrare
...

Per decifrare
...

dove in modulo n e deve essere trovato utilizzando l'algoritmo esteso di Euclide.