Algoritmo esteso di Euclide

In aritmetica e nella programmazione lTemplate:'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,\dots ,q_k$ dei quozienti e $r_0,\dots ,r_{k+1}$ dei resti come segue:

$\begin{array}{cc}{q}_1& =a:b\\ & ⋮\\ q_i& =r_{i-1}:r_i\\ & ⋮\end{array}$ $\begin{array}{cc}{r}_0& =a\\ r_1& =b\\ & ⋮\\ r_{i+1}& =r_{i-1}-q_i{r}_i\\ & ⋮\end{array}$

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,\dots ,x_k$ e $y_0,\dots ,y_k$ tali che:

$\begin{array}{cc}{x}_0& =1\\ x_1& =0\\ & ⋮\\ x_{i+1}& =x_{i-1}-q_i{x}_i\\ & ⋮\end{array}$$\begin{array}{cc}{y}_0& =0\\ y_1& =1\\ & ⋮\\ y_{i+1}& =y_{i-1}-q_i{y}_i\\ & ⋮\end{array}$

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=\mathrm{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 1mod7$
• 3 è l'inverso moltiplicativo di 7 modulo 20, cioè $7\times 3\equiv 1mod20$ .

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

• Template:Cita libro