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 x e y dell'identità di Bézout.

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.

Storia

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.

Descrizione

Dati due numeri interi a e b, l'algoritmo di Euclide permette di calcolare le sequenze $q_{1},\ldots ,q_{k}$ dei quozienti e $r_{0},\ldots ,r_{k+1}$ dei resti come segue:

${\begin{aligned}q_{1}&=a:b\\&\,\,\,\vdots \\q_{i}&=r_{i-1}:r_{i}\\&\,\,\,\vdots \end{aligned}}$ ${\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}\\&\,\,\,\vdots \end{aligned}}$

La sequenza si arresta quando $r_{k+1}=0$ e il MCD corrisponde a $r_{k}$.

L'algoritmo esteso di Euclide procede in modo simile: si considerano due ulteriori sequenze $x_{0},\ldots ,x_{k}$ e $y_{0},\ldots ,y_{k}$ tali che:

${\begin{aligned}x_{0}&=1\\x_{1}&=0\\&\,\,\,\vdots \\x_{i+1}&=x_{i-1}-q_{i}x_{i}\\&\,\,\,\vdots \end{aligned}}$${\begin{aligned}y_{0}&=0\\y_{1}&=1\\&\,\,\,\vdots \\y_{i+1}&=y_{i-1}-q_{i}y_{i}\\&\,\,\,\vdots \end{aligned}}$

Al termine dell'algoritmo, i coefficienti dell'identità di Bézout sono $x_{k}$ e $y_{k}$.

Esempio

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 k. 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 che $ax+by=\operatorname {MCD} (a,b)$ poiché $20\times (-1)+7\times 3=1.$

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è $20\times (-1)\equiv 1\mod 7$
• 3 è l'inverso moltiplicativo di 7 modulo 20, cioè $7\times 3\equiv 1\mod 20$ .

Applicazioni

L'algoritmo di Euclide trova 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.

Bibliografia

• (EN) Donald Knuth, Seminumerical Algorithms, in The Art of Computer Programming, vol. 2, Addison-Wesley, 1997.