Utente:Grasso Luigi/sandbox4/Algoritmo esteso di Euclide

In aritmetica e nella programmazione l'algoritmo esteso di Euclide ( abbreviato:EEA) è 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 due insiemi di successioni di numeri interi $Q\ ,R$ dette dei quozienti e dei resti. Prendiamo come indice la variabile che denotiamo $k$. L'algoritmo indica il calcolo dei resti intermedi $r_{k}$ tramite una divisione-con-resto sulla coppia precedente $(r_{k-2},\ r_{k-1})$ ottenendo un quoziente $q_{k}\in \mathbb {Z}$ tale che:

$r_{k-2}=q_{k}\cdot r_{k-1}+r_{k}\qquad 0\leq r_{k}<r_{k-1}\quad k=0,1,2,\ldots ,n\quad (*)$

cioè

${\begin{aligned}k&=0&&r_{-2}=q_{0}\ r_{-1}\ +r_{0};&&a=q_{0}\ b\ +r_{0}\\k&=1&&r_{-1}=q_{1}\ r_{0}\ +r_{1};&&b=q_{1}\ r_{0}\ +r_{1}\\k&=2&&r_{0}=q_{2}\ r_{1}\ +r_{2}&&\\&\vdots &&\vdots &&\\k&=n-1&&r_{n-3}=q_{n-1}\ r_{n-2}\ +r_{n-1}&&\\k&=n&&r_{n-2}=q_{n}\ r_{n-1}\ +r_{n};&&r_{n-2}=q_{n}\ r_{n-1}\\\end{aligned}}$

quindi otteniamo le due successioni d'interi:

$R\ =\ \{r_{-2}=a,\ r_{-1}=b,\ r_{0},\ r_{1},\ \cdots ,\ r_{n-1},\ r_{n}=0\}\qquad r_{k+1}<r_{k}\qquad Q\ =\ \{q_{0},\ q_{1},\ \cdots ,\ q_{n-1},\ q_{n}\}$.

Il calcolo si ferma quando si raggiunge un resto nullo $r_{n}=0$; allora il massimo comune divisore ha il valore

$\operatorname {MCD} \ (a,\ b)\ =r_{n-1}.$

Con un cambio dell'indice del tipo $i\ =k-1$, la (*) diventa

$r_{i-1}=q_{i+1}\cdot r_{i}+r_{i+1}\qquad 0\leq r_{i+1}<r_{i}$

che si può mettere nella forma

$r_{i+1}=-q_{i+1}\cdot r_{i}+r_{i-1}.$

con le relative successioni

$R\ =\ \{r_{-1}=a,\ r_{0}=b,\ r_{1},\ r_{2},\ \cdots ,\ r_{n},\ r_{n+1}=0\}\qquad r_{i+2}<r_{i+1}\qquad Q\ =\ \{q_{1},\ q_{2},\ \cdots ,\ q_{n},\ q_{n+1}\}$.

L'algoritmo esteso di Euclide procede in modo simile: si considerano oltre a $Q\ ,R$ due ulteriori insiemi di successioni di numeri interi $X\ ,Y$ dette coefficienti di Bézout tali che:

${\begin{aligned}x_{i+1}&=-q_{i+1}\cdot x_{i}+x_{i-1}\quad i=0,1,2,\ldots ,n\quad (**)\\y_{i+1}&=-q_{i+1}\cdot y_{i}+y_{i-1}\\\end{aligned}}$

cioè

${\begin{aligned}i&=0&&x_{1}=-q_{1}\ x_{0}\ +x_{-1}=-q_{1}\ 0\ +1=1&&y_{1}=-q_{1}\ y_{0}\ +y_{-1}=-q_{1}\ 1\ +0=-q_{1}\\i&=1&&x_{2}=-q_{2}\ x_{1}\ +x_{0}=-q_{2}\ 1\ +0=-q_{2}&&y_{2}=-q_{2}\ y_{1}\ +y_{0}=-q_{2}\ -q_{1}\ +1=q_{2}q_{1}+1\\i&=2&&x_{3}=-q_{3}\ x_{2}\ +x_{1}=-q_{3}\ -q_{1}\ +1=q_{3}q_{1}+1&&y_{3}=-q_{3}\ y_{2}\ +y_{1}=-q_{3}\ (q_{2}q_{1}+1)-q_{1}=-q_{3}q_{2}q_{1}-q_{3}-q_{1}\\&\vdots &&\,\,\vdots &&\,\,\vdots \\i&=n-1&&x_{n}=-q_{n}\ x_{n-1}\ +x_{n-2}&&y_{n}=-q_{n}\ y_{n-1}\ +y_{n-2}\\i&=n&&x_{n+1}=-q_{n+1}\ x_{n}\ +x_{n-1}&&y_{n+1}=-q_{n+1}\ y_{n}\ +y_{n-1}\\\end{aligned}}$

quindi otteniamo le due successioni d'interi:

$X\ =\ \{x_{-1}=1,\ x_{0}=0,\ x_{1},\ x_{2},\ \cdots ,\ x_{n},\ x_{n+1}\}\qquad Y\ =\ \{y_{-1}=0,\ y_{0}=1,\ y_{1},\ y_{2},\ \cdots ,\ y_{n},\ y_{n+1}\}$.

Al termine dell'algoritmo, i coefficienti dell'identità di Bézout sono $x_{n},\ y_{n}$. Il calcolo si ferma quando si raggiunge un resto nullo $r_{n+1}\ =0$ e permette di ottenere

• $r_{n}$ è il massimo comune divisore dell’input $a\ =r_{-1},\ b\ =r_{0}.$

  $\operatorname {MCD} \ (a,\ b)\ =r_{n}$

• $(x_{n},\ y_{n})$ sono i coefficienti di Bézout dell'identità di Bézout:

  $\operatorname {MCD} \ (a,\ b)\ =r_{n}\ =ax_{n}\ +by_{n}$

  in particolare se $a,\ b\in \mathbf {P} \quad (r_{n}=1)$ si verificano le relazioni

  ${\begin{aligned}a\ x_{n}&\equiv 1{\pmod {b}}\implies x_{n}\equiv a^{-1}{\pmod {b}}\\b\ y_{n}&\equiv 1{\pmod {a}}\implies y_{n}\equiv b^{-1}{\pmod {a}}\\\end{aligned}}$

  x_n è l'inverso moltiplicativo di a modulo b, oppure y_n è l'inverso rispetto operazione di b modulo a

• $(x_{n+1}\ ,y_{n+1})$ sono i quozienti di a e b quando li dividiamo per il loro massimo comun divisore, cioè:

  $(x_{n+1}\ ,y_{n+1})\ =\left(\pm {\frac {b}{r_{n}}}\ ,\pm {\frac {a}{r_{n}}}\right)$

• Inoltre, se $a,\ b\in \mathbb {Z} ^{+}\quad \operatorname {MCD} \ (a,\ b)\ \neq \min \ (a,\ b)$, allora

  $|x_{i}|\leq \left\lfloor {\frac {b}{2\ r_{n}}}\right\rfloor ,\qquad |y_{i}|\leq \left\lfloor {\frac {a}{2\ r_{n}}}\right\rfloor \quad 0\leq i\leq n,$

  dove $\lfloor x\rfloor$ denota la parte intera dell'intero x, cioè il più grande intero non maggiore di x. Ciò implica che la coppia di coefficienti di Bézout fornita dall'algoritmo euclideo esteso è la coppia minima, in quanto è l'unica coppia che soddisfa entrambe le disuguaglianze di cui sopra.

Da quanto visto l'algoritmo può essere eseguito senza overflow da un programma per computer utilizzando numeri interi di dimensione fissa maggiore di quella di a e b.

Esempi

• :$(a,\ b)\ =(240,\ 46)$
  La tabella seguente mostra come procede l'algoritmo euclideo esteso con gli input $a=240,\ b=46$. Il massimo comun divisore è l'ultimo numero diverso da zero, 2 nella colonna "resto". Il calcolo si ferma per n=4, poichè il resto è 0. I coefficienti Bézout $(x_{n},\ y_{n})=(-9,47)$ compaiono nelle ultime due colonne della penultima riga, inoltre i due valori $(x_{n+1},\ y_{n+1})=(23,-120)$ dell'ultima riga sono, compreso il segno, i quozienti delle divisioni 46 e 240 per il massimo comun divisore 2. Cioè si ha

  $MCD\ (a,\ b)=(240,\ 46)=2$

  $a\ x_{n}+b\ y_{n}\ =240\cdot (-9)+46\cdot 47=\operatorname {MCD} (a,b)\ =r_{n}\ =2$.

  $(x_{n+1},\ y_{n+1})\ =(23,\ -120)\ =\left({\frac {46}{2}},\ -{\frac {240}{2}}\right)$

  $\left\lfloor {\frac {b}{2\ r_{n}}}\right\rfloor =\left\lfloor {\frac {46}{4}}\right\rfloor =11\qquad \left\lfloor {\frac {a}{2\ r_{n}}}\right\rfloor =\left\lfloor {\frac {240}{4}}\right\rfloor =60,\quad \min \ (a,\ b)=46\neq r_{n}=2$

  indice	quoziente	resto	Coefficienti Bézout
  i	qi+1	ri+1	xi+1	yi+1
  		r-1 = 240	x-1 = 1	y-1 =0
  		r0 = 46	x0 = 0	y0 =1
  0	240 ÷ 46 = 5	240 − 5 · 46 = 10	1 − 5 · 0 = 1	0 − 5 · 1 = −5
  1	46 ÷ 10 = 4	46− 4 · 10= 6	0 − 4 · 1 = −4	1 − 4 · −5 = 21
  2	10 ÷ 6 = 1	10 − 1 · 6 = 4	1 − 1 · −4 = 5	−5 − 1 ·t 21 = −26
  3	6 ÷ 4 = 1	6 − 1 · 4 = 2	−4 − 1 · 5 = −9	21 − 1 · −26 = 47
  n=4	4 ÷ 2 = 2	4 − 2 · 2 = 0	5 − 2 · −9 = 23	−26 − 2 · 47 = −120

  ottenendo le sequenze

  $R\ =\ \{r_{-1}=a,\ r_{0}=b,\ r_{1},\ r_{2},\ r_{3},\ r_{4},\ r_{5}=0\}=\ \{240,\ 46,\ 10,\ 6,\ 4,\ 2,\ 0\}$

  $Q\ =\ \{q_{1},\ q_{2},\ q_{3},\ q_{4},\ q_{5}\}=\ \{5,\ 4,\ 1,\ 1,\ 2\}$

  $X\ =\ \{x_{-1}=1,\ x_{0}=0,\ x_{1},\ x_{2},\ x_{3},\ x_{4},\ x_{5}\}=\ \{1,\ 0,\ 1,-4,\ 5,-9,\ 23\}$

  $Y\ =\ \{y_{-1}=0,\ y_{0}=1,\ y_{1},\ y_{2},\ y_{3},\ y_{4},\ y_{5}\}=\ \{0,\ 1,-5,\ 21,-26,\ 47,-120\}.$

  Si verifica facilmente la proprietà per le sequenze coefficienti Bèzout dei valori assoluti

  $|X|\ =\ \{|x_{i}|,\ 0\leq i\leq n=4\}=\{1,\ 0,\ 1,\ 4,\ 5,\ 9\}$ con $|x_{i}|\leq \left\lfloor {\frac {46}{4}}\right\rfloor =11$

  $|Y|\ =\ \{|y_{i}|,\ 0\leq i\leq n=4\}=\{0,\ 1,\ 5,\ 21,\ 26,\ 47\}$ con $|y_{i}|\leq \left\lfloor {\frac {240}{4}}\right\rfloor =60$

• :$(a,\ b)\ =(20,\ 7)$
  La seguente tabella mostra con un esempio come procede l'algoritmo esteso di Euclide nel caso dei numeri $a=20,\ b=7$. Il calcolo procede con una serie di iterazioni i da 0 a n. Si arresta quando è nullo il risultato nella colonna "resto" (r_n+1 = r₃ = 0).I coefficienti di Bézout sono i risultati nelle ultime due colonne della penultima riga. I risultati delle ultime due colonne nell'ultima riga, 7 e −20, sono rispettivamente, con il segno, i quozienti di 7 e 20 rispetto al massimo comun divisore 1. Riassumendo:

  $\operatorname {MCD} \ (a,\ b)\ =(20,\ 7)=1\quad 20,7\in \mathbf {P}$

  $a\ x_{n}+b\ y_{n}\ =20\cdot (-1)+7\cdot 3\ =\operatorname {MCD} (a,b)\ =r_{n}\ =1$

  $(x_{n+1},\ y_{n+1})\ =(7,\ -20)\ =\left({\frac {7}{1}},\ -{\frac {20}{1}}\right)$

  $\left\lfloor {\frac {b}{2\ r_{n}}}\right\rfloor =\left\lfloor {\frac {7}{2}}\right\rfloor =3\qquad \left\lfloor {\frac {a}{2\ r_{n}}}\right\rfloor =\left\lfloor {\frac {20}{2}}\right\rfloor =10,\quad \min \ (a,\ b)=7\neq r_{n}=1$

  quindi 20 e 7 sono coprimi.

  indice	quoziente	resto	Coefficienti Bézout
  i	qi+1	ri+1	xi+1	yi+1
  		r-1 = 20	x-1 = 1	y-1 =0
  		r0 = 7	x0 = 0	y0 =1
  0	20 ÷ 7 = 2	20 − 2 · 7 = 6	1 − 2 · 0 = 1	0 − 2 · 1 = −2
  1	7 ÷ 6 = 1	7 − 1 · 6 = 1	0 − 1 · 1 = −1	1 − 1 · (−2) = 3
  n=2	6 ÷ 1 = 6	6 − 6 · 1 = 0	1 − 6 · (−1) = 7	−2 − 6 · 3 = −20
  $a\ x_{n}+b\ y_{n}=20\cdot (-1)+7\cdot 3=1=r_{n}$

  ottenendo le sequenze

  $R\ =\ \{r_{-1}=a,\ r_{0}=b,\ r_{1},\ r_{2},\ r_{3}=0\}=\ \{20,\ 7,\ 6,\ 1,\ 0\}$

  $Q\ =\ \{q_{1},\ q_{2},\ q_{3}\}=\ \{2,\ 1,\ 6\}$

  $X\ =\ \{x_{-1}=1,\ x_{0}=0,\ x_{1},\ x_{2},\ x_{3}\}=\ \{1,\ 0,\ 1,\ -1,\ 7\}$

  $Y\ =\ \{y_{-1}=0,\ y_{0}=1,\ y_{1},\ y_{2},\ y_{3}\}=\ \{0,\ 1,\ -2,\ 3,\ -20\}.$

  Si verifica facilmente la proprietà per le sequenze coefficienti Bèzout dei valori assoluti

  $|X|\ =\ \{|x_{i}|,\ 0\leq i\leq n=2\}=\{1,\ 0,\ 1,\ 1\}$ con $|x_{i}|\leq \left\lfloor {\frac {7}{2}}\right\rfloor =3$

  $|Y|\ =\ \{|y_{i}|,\ 0\leq i\leq n=2\}=\{0,\ 1,\ 2,\ 3\}$ con $|y_{i}|\leq \left\lfloor {\frac {20}{2}}\right\rfloor =10.$

  Essendo i due numeri coprimi si ha anche:

  $a\ x_{n}\equiv 1{\pmod {b}};\quad 20\cdot -1\equiv 1{\pmod {7}}$

  $b\ y_{n}\equiv 1{\pmod {a}};\quad 7\cdot 3\equiv 1{\pmod {20}}$

  -1 è l'inverso moltiplicativo di 20 modulo 7 e 3 è l'inverso moltiplicativo di 7 modulo 20.

Dimostrazione

• $\operatorname {MCD} \ (a,\ b)\ =r_{n}\ =ax_{n}\ +by_{n}$

  Una successione limitata $0\leq r_{i+1}<|r_{i}|,$ dei resti $r_{i}$ ha carattere decrescente con tutti i termini non negativi ($i\geq 2$) quindi ammette un limite inferiore e deve fermarsi con qualche $r_{n+1}=0.$ Ciò dimostra che l'algoritmo prima o poi si ferma.

  Quando

  $r_{i+1}=-r_{i}q_{i+1}\ +r_{i-1},$

  allora $\operatorname {MCD} \ (r_{i-1},\ r_{i})=\operatorname {MCD} \ (r_{i},\ r_{i+1}).$

  Ciò dimostra che $\operatorname {MCD} \ (a=r_{-1},\ b=r_{0})=\operatorname {MCD} \ (r_{n},\ r_{n+1}=0)=r_{n}$ e quindi $r_{n}$ è il massimo comune divisore di a and b. (Fino a questo punto la dimostrazione è la stessa dell’algoritmo euclideo classico.)

  L'input $(a=r_{-1},\ b=r_{0})$ si ottiene dalla

  $ax_{i}\ +by_{i}\ =r_{i}\quad {\mbox{ per i valori }}\quad i=0,\ (x_{-1},\ y_{-1})=(1,0)\quad \quad i=1,\ (x_{0},\ y_{0})=(0,1).$

  La relazione segue per induzione per ogni $i>1$:

  $r_{i+1}\ =r_{i-1}-r_{i}q_{i+1}\ =(ax_{i-1}\ +by_{i-1})\ -(ax_{i}\ +by_{i})\ q_{i+1}=(ax_{i-1}\ -ax_{i}q_{i+1})\ +(by_{i-1}\ -by_{i}q_{i+1})\ =ax_{i+1}\ +by_{i+1}.$

  in particolare si ha

  ${\begin{aligned}r_{n}&=ax_{n}\ +by_{n},&i&=n-1\\r_{n+1}&=ax_{n+1}\ +by_{n+1}\ =0,&i&=n\\\end{aligned}}$.

• $(x_{n+1}\ ,y_{n+1})\ =\left(\pm {\frac {b}{r_{n}}}\ ,\pm {\frac {a}{r_{n}}}\right)$

  Definiamo la seguente matrice dei coefficienti

  $A_{i}\ ={\begin{pmatrix}x_{i-1}&x_{i}\\y_{i-1}&y_{i}\end{pmatrix}}\qquad \left|A_{i}\right|\ =x_{i-1}y_{i}\ -x_{i}y_{i-1}$

  e la relazione di ricorrenza in forma di matrice diventa

  $A_{i+1}\ =A_{i}\cdot {\begin{pmatrix}0&1\\1&-q_{i}\end{pmatrix}}\qquad \left|A_{i+1}\right|\ =-\left|A_{i}\right|$

  la matrice iniziale per i = 0 è quella identica

  $A_{1}\ ={\begin{pmatrix}1&0\\0&1\end{pmatrix}}\qquad \left|A_{1}\right|\ =1$

  quindi ne segue che

  $\left|A_{i}\right|\ =(-1)^{i-1}.$

  In particolare, per $i\ =n+1,$ abbiamo $\left|A_{n+1}\right|\ =x_{n}y_{n+1}-y_{n}x_{n+1}=(-1)^{n}.$

  Considerandola come l'identità di Bézout, si dimostra che $x_{n+1},\ y_{n+1}$ sono coprimi. Infatti la relazione provata in precedenza

  $ax_{n+1}\ +by_{n+1}\ =0\quad {\mbox{(*)}}$

  e il lemma di Euclide indicano $x_{n+1}\mid b$ (sono divisibili)

  $\exists \ d\in \mathbb {Z} \ :b\ =d\ x_{n+1}$

  adesso dividendo per $x_{n+1}$ la relazione (*) si ottiene

  $a\ +b\ {\frac {y_{n+1}}{x_{n+1}}}\ =0;\quad a\ =-y_{n+1}\ b\ {\frac {d}{b}}\ =-d\ y_{n+1}$

  in conclusione, $x_{n+1}$ e $-y_{n+1}$ sono interi coprimi e corrispondono ai quozienti di a e b per un fattore comune, che può essere o il loro massimo comun divisore o l'opposto.

• $a,\ b\in \mathbb {Z} ^{+}\quad \operatorname {MCD} \ (a,\ b)\neq \min \ (a,\ b)\implies \qquad |x_{i}|\leq \left\lfloor {\frac {b}{2\ r_{n}}}\right\rfloor ,\qquad |y_{i}|\leq \left\lfloor {\frac {a}{2\ r_{n}}}\right\rfloor \quad 0\leq i\leq k,$

  Allora $a\neq b$, e se $a<b$, si può vedere che le sequenze $X,\ Y$ per l'input (a,b) coincidono, compreso i valori iniziali 0 e 1, con le sequenze $Y,\ X$ per l'input (b,a). Quindi il caso (a,b) si riduce al caso (b,a). Allora ipotizziamo $a>b$ senza perdita di generalità.

  Notiamo che $x_{2}\ =1,\quad x_{3}<0$ (x₃ esiste essendo $r_{n}\neq \min(a,\ b)$). Successivamente, gli $x_{i}$ si alternano di segno e aumentano strettamente di valore, che segue induttivamente dalle definizioni e dal fatto che $q_{i}\geq 1\quad 1\leq i\leq n$, compreso il caso $i=1$. Lo stesso ragionamento vale per $y_{i}$. Inoltre è facile vedere che $q_{n}\geq 2$. Quindi, essendo

  $|x_{n+1}|=|x_{n-1}|+q_{n}|x_{n}|\qquad |y_{n+1}|=|y_{n-1}|+q_{n}|y_{n}|$

  si ottengono

  $2|x_{n}|\leq q_{n}|x_{n}|\leq \left|{\frac {b}{r_{n}}}\right|\ =|x_{n+1}|\qquad \qquad 2|y_{n}|\leq q_{n}|y_{n}|\leq \left|{\frac {a}{r_{n}}}\right|=|y_{n+1}|$

  inoltre $x_{n},\ y_{n}$ sono maggiori o uguali in valore assoluto rispetto a qualsiasi precedente $x_{i},\ y_{i}$, cioè

  $x_{i}\leq |x_{i}|\leq |x_{n}|\qquad y_{i}\leq |y_{i}|\leq |y_{n}|\quad \forall \ 0\leq i\leq n$

  queste due ultime relazioni portano alla tesi.

EEA polinomiale

Per i polinomi univariatil con in coefficienti in un campo, tutto funziona allo stesso modo: la divisione euclidea, l'identità di Bézout e l'algoritmo esteso di Euclide. Vediamo di confrontare.

MCD interi, MCD polinomiale

La prima differenza è che, nella divisione euclidea e nell'algoritmo, la disuguaglianza $0\leq r_{i+1}<|r_{i}|$ viene sostituita come disuguaglianze sul grado $\deg r_{i+1}<\deg r_{i}.$ Altrimenti tutto ciò che precede in questo articolo rimane lo stesso, semplicemente sostituendo gli interi con i polinomi.

Una seconda differenza risiede nel limite alla dimensione dei coefficienti di Bézout fornito dall'algoritmo euclideo esteso, che è più accurato nel caso polinomiale, portando al seguente teorema:

Se a, b sono due polinomi non nulli, allora EEA produce una sola coppia di polimoni (s, t) tali che $a\ s\ +b\ t\ =\operatorname {MCD} \ (a,\ b)\quad$ e $\quad \deg s<\deg b-\deg(\operatorname {MCD} \ (a,\ b)),\quad \deg t<\deg a-\deg(\operatorname {MCD} \ (a,\ b)\ ).$

Una terza differenza è che, nel caso polinomiale, il massimo comun divisore è definito solo fino alla moltiplicazione per una costante diversa da zero. Esistono diversi modi per definire in modo inequivocabile un massimo comun divisore.

Normalizzazione MCD

• In matematica, è comune richiedere che il massimo comun divisore sia un polinomio monico. Per ottenere ciò è sufficiente dividere ogni elemento dell'output per il coefficiente principale di $r_{n}.$ Ciò consente, se a e b sono coprimi, di ottenere 1 nel membro destro della disuguaglianza di Bézout. Altrimenti si potrebbe ottenere qualsiasi costante diversa da zero. In algebra computazionale, i polinomi hanno comunemente coefficienti interi, e questo modo di normalizzare il massimo comun divisore ha l'effetto d'introdurre troppe frazioni.]], i polinomi hanno comunemente coefficienti interi, e questo modo di normalizzare il massimo comun divisore ha l'effetto d'introdurre troppe frazioni.

• Il secondo modo per normalizzare MCD nel caso di polinomi a coefficienti interi è dividere ogni output per il contenuto di $r_{n},$ per ottenere il polinomio primitivo MCD. Se i polinomi di input sono coprimi, questa normalizzazione fornisce anche

  $\operatorname {\ } {MCD}(a,\ b)\ =1.$

Lo svantaggio di questo metodo è il calcolo e la semplificazione di molte frazioni.

• Un terzo metodo consiste nell'estendere l'algoritmo della successione dei pseudo-resti in modo simile all'estensione dell'algoritmo euclideo all'algoritmo euclideo esteso. Con questo metodo quando si inizia con polinomi a coefficienti interi, tutti i polinomi calcolati restano con i coefficienti interi. Inoltre, ogni resto calcolato $r_{i}$ è un polinomio sottorisultante. In particolare, se i polinomi di input sono coprimi, allora l'identità di Bézout diventa:

$a\ s\ +b\ t\ =\operatorname {Res} \ (a,\ b),$

dove $\operatorname {Res} \ (a,\ b)$ denota il risultante di a e b. In questa forma dell'identità di Bézout, non c'è alcun denominatore nella formula. Se si divide tutto per la risultante si ottiene l'identità classica di Bézout, con un esplicito denominatore comune per i numeri razionali che vi compaiono.

Pseudocodice

In questa sezione e nelle successive, div è una funzione ausiliaria che calcola il quoziente della divisione euclidea del suo argomento di sinistra con il suo argomento di destra.

Per implementare l'algoritmo sopra descritto, occorre innanzitutto osservare che in ogni passaggio sono necessari solo gli ultimi due valori delle variabili indicizzate. Pertanto, per risparmiare memoria, ciascuna variabile indicizzata deve essere sostituita solo da due variabili. Per semplicità, gli algoritmi che descriviamo utilizzano assegnazioni parallele. In un linguaggio di programmazione che non dispone di questa funzionalità, le assegnazioni parallele vengono simulate con una variabile ausiliaria. Ad esempio, le assegnazioni

(old_r, r) := (r, old_r - quotient * r)

si ottiene usando la variabile ausiliaria prov

prov := r; r := old_r - quotient × prov; old_r := prov;

e lo stesso per altri assegnamenti. Otteniamo il codice seguente:

 '''function''' extended_gcd(a, b)
     (old_r, r) := (a, b)
     (old_s, s) := (1, 0)
     (old_t, t) := (0, 1)
     
     '''while''' r ≠ 0 '''do'''
         quotient := old_r '''div''' r
         (old_r, r) := (r, old_r − quotient × r)
         (old_s, s) := (s, old_s − quotient × s)
         (old_t, t) := (t, old_t − quotient × t)
     
     '''output''' "coefficienti Bézout i=n:", (old_s, old_t)
     '''output''' "massimo comune divisore:", old_r
     '''output''' "coefficienti Bèzout i=n+1:", (t, s)

I quozienti di a e b ottenuti per il loro massimo comun divisore, visualizzati, potrebbero avere un segno errato. Questo è facile da correggere alla fine del calcolo ma non viene fatto per semplificare il codice. Allo stesso modo, se a o b è zero e l'altro è negativo, il massimo comun divisore restituito è negativo e tutti i segni dell'output devono essere modificati.

Infine, notare che nell'identità di Bézout

$ax\ +by\ =\operatorname {MCD} \ (a,\ b)\ =r_{n}$

possiamo risolvere in $y$ essendo dati $a,b,x,r_{n}$. Quindi, possiamo ottimizzare l'algoritmo precedente calcolando solo la sequenza $x_{i}$ (che produce il coefficiente di Bézout $x_{n}$), e infine calcolare $y_{n}$:

 '''function''' extended_gcd(a, b)
     s := 0;    old_s := 1
     r := b;    old_r := a
          
     '''while''' r ≠ 0 '''do'''
         quotient := old_r '''div''' r
         (old_r, r) := (r, old_r − quotient × r)
         (old_s, s) := (s, old_s − quotient × s)
     
     '''if''' b ≠ 0 '''then'''
         bezout_t := (old_r − old_s × a) '''div''' b
     '''else'''
         bezout_t := 0
     
     '''output''' "coefficienti Bézout i=n:", (old_s, bezout_t)
     '''output''' "massimo comune divisore:", old_r

Tuttavia, in molti casi questa non è realmente un'ottimizzazione: mentre il primo algoritmo non è suscettibile di overflow quando utilizzato con numeri interi macchina (cioè numeri interi con un limite superiore fisso di cifre), la moltiplicazione di old_s * a nel calcolo di bezout_t può traboccare, limitando questa ottimizzazione agli input che possono essere rappresentati in meno della metà della dimensione massima. Quando si utilizzano numeri interi di dimensione illimitata, il tempo necessario per la moltiplicazione e la divisione cresce quadraticamente con la loro dimensione. Ciò implica che l'"ottimizzazione" sostituisce una sequenza di moltiplicazioni/divisioni di piccoli numeri interi al posto di un'unica moltiplicazione/divisione, questo comporta un tempo di calcolo superiore rispetto alle operazioni sostituite.

EEA generalizzato

È possibile generalizzare l'algoritmo al caso di più di due numeri in modo iterativo.

All'inizio consideriamo n= 3 numeri $a,\ b,\ c$ e vogliamo provare

$\operatorname {MCD} \ (a,\ b,\ c)\ =\operatorname {MCD} \ \left(\operatorname {MCD} \ (a,\ b),\ c\right)$.

Supponiamo che $d\ =\operatorname {MCD} \ (a,\ b,\ c)$. Per definizione di MCD $d$ è divisore di $a$ e $b$. Cioè:

$\exists k\in \mathbb {Z} \ :\operatorname {MCD} \ (a,\ b)\ =k\cdot d$

inoltre $d$ è divisore di $c$ cioè:

$\exists j\in \mathbb {Z} \ :c\ =j\cdot d$.

Let $u=\gcd(k,j)$. By our construction of $u$, $ud|a,b,c$ but since $d$ is the greatest divisor $u$ is a unit. And since $ud=\gcd(\gcd(a,b),c)$ the result is proven.

Se la coppia di coefficienti Bèzout $(n,\ m)$ danno l'identità

$n\cdot a\ +m\cdot b\ =\operatorname {MCD} \ (a,\ b)$

allora vi è pure una coppia $(x,\ y)$ per cui vale l'identità

$x\ \operatorname {MCD} \ (a,\ b)+y\ c=\operatorname {MCD} \ (a,\ b,\ c)$

ottenendo l'identità di Bèzout per n= 3 numeri

$x\ (na+mb)+yc\ =(xn)a+(xm)b+yc=x_{a}a+x_{b}b+x_{c}c=\operatorname {MCD} \ (a,\ b,\ c)=\operatorname {MCD} \ (a,\ \operatorname {MCD} \ (b,\ c)).$

Allora per applicarlo ad n numeri $a_{1},a_{2},\dots ,a_{n}$ usiamo il principio di induzione

$\operatorname {MCD} \ (a_{1},\ a_{2},\dots ,\ a_{n})\ =\operatorname {MCD} \ (a_{1},\,\operatorname {MCD} \ (a_{2},\,\operatorname {MCD} \ (a_{3},\dots ,\operatorname {MCD} \ (a_{n-1}\,,a_{n})))\dots ),$

mentre l'identità di Bèzout con coefficienti $(x_{1},\ x_{2},\dots ,x_{n})$ diventa

$x_{1}a_{1}\ +x_{2}a_{2}\ +\dots +x_{n}a_{n}\ =\operatorname {MCD} \ (a_{1},\ a_{2},\dots ,\ a_{n})$

con le equazioni che seguono direttamente.

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.
• (EN) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Section 31.2: Greatest common divisor, in Introduction to Algorithms, MIT Press, McGraw-Hill, 2001, pp. 859–861, ISBN 0-262-03293-7.

Voci correlate

• Dominio euclideo
• Teorema della congruenza lineare
• Kuṭṭaka