Algoritmo esteso di Euclide

In aritmetica e nella programmazione l'algoritmo esteso di Euclide è un'estensione dell'algoritmo di Euclide che calcola non solo il massimo comun divisore (indicato con MCD nel seguito) tra due interi a e b, ma anche i coefficienti dell'identità di Bézout x e y tali che:

L'algoritmo esteso di Euclide è particolarmente utile quando a e b sono interi coprimi: in questo caso x è l'inverso moltiplicativo di a modulo b e y è l'inverso moltiplicativo di b modulo a.

Spesso si indica con l'espressione algoritmo esteso di Euclide anche un altro algoritmo, molto simile al precedente, per il calcolo del massimo comun divisore tra polinomi e i loro coefficienti dell'identità di Bézout.

Entrambi gli algoritmi trovano applicazione nella crittografia, in particolare il calcolo dell'inverso moltiplicativo modulare è un passo fondamentale per criptare i messaggi con l'algoritmo a chiave pubblica RSA.

Le prime documentazioni sull'algoritmo risalgono al V-VI secolo a.C., ad opera del matematico indiano Aryabhata. Fu poi riscoperto più volte indipendentemente, ad esempio dal francese Bachet nel 1621 e poi da Eulero intorno al 1731[1].

EsempioModifica

La seguente tabella mostra con un esempio come procede l'algoritmo esteso di Euclide nel caso dei numeri 20 e 7.

Il calcolo procede con una serie di iterazioni i da 0 a n. Si arresta quando è nullo il risultato nella colonna "resto" (alla riga 4 nell'esempio), per cui il massimo comun divisore è 1 e quindi 20 e 7 sono coprimi.

I coefficienti di Bézout sono i risultati nelle ultime due colonne della penultima riga. Infatti, è facile verificare l'identità:

  diventa  

I risultati delle ultime due colonne nell'ultima riga, 7 e −20, sono rispettivamente, segno a parte, i quozienti di 7 e 20 rispetto al massimo comun divisore 1.

indice i quoziente qi-1 resto ri xi yi
0 20 1 0
1 7 0 1
2 20 ÷ 7 = 2 20 − 2 × 7 = 6 1 − 2 × 0 = 1 0 − 2 × 1 = −2
3 7 ÷ 6 = 1 7 − 1 × 6 = 1 0 − 1 × 1 = −1 1 − 1 × (−2) = 3
4 6 ÷ 1 = 6 6 − 6 × 1 = 0 1 − 6 × (−1) = 7 −2 − 6 × 3 = −20

Essendo i due numeri coprimi si ha anche:

  • -1 è l'inverso moltiplicativo di 20 modulo 7, cioè  
  •  3 è l'inverso moltiplicativo di 7 modulo 20, cioè   .

NoteModifica

  1. ^ André Weil, Number Theory, Birkhäuser, 2001, pp. 6-7, 176-77, ISBN 978-0-8176-4571-7.