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^[1].

Descrizione

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

${\displaystyle {\begin{aligned}q_{1}&=a:b\\&\,\,\,\vdots \\q_{i}&=r_{i-1}:r_{i}\\&\,\,\,\vdots \end{aligned}}}$ ${\displaystyle {\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 ${\displaystyle r_{k+1}=0}$ e il MCD corrisponde a ${\displaystyle r_{k}}$.

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

${\displaystyle {\begin{aligned}x_{0}&=1\\x_{1}&=0\\&\,\,\,\vdots \\x_{i+1}&=x_{i-1}-q_{i}x_{i}\\&\,\,\,\vdots \end{aligned}}}$${\displaystyle {\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 ${\displaystyle x_{k}}$ e ${\displaystyle 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 ${\displaystyle ax+by=\operatorname {MCD} (a,b)}$ poiché ${\displaystyle 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è ${\displaystyle 20\times (-1)\equiv 1\mod 7}$
• 3 è l'inverso moltiplicativo di 7 modulo 20, cioè ${\displaystyle 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.