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 q 1 , … , q k {\displaystyle q_{1},\ldots ,q_{k}} dei quozienti e r 0 , … , r k + 1 {\displaystyle r_{0},\ldots ,r_{k+1}} dei resti come segue:

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

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

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

Note

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

Bibliografia

  Portale Crittografia
  Portale Matematica