Algoritmo esteso di Euclide: differenze tra le versioni

Versione delle 11:35, 29 ago 2020

Versione attuale delle 03:36, 31 ott 2024

(14 versioni intermedie di 6 utenti non mostrate)

Riga 1:

In [[aritmetica]] e nella [[Programmazione (informatica)|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 dell'[[identità di Bézout]] ''x'' e ''y'' talidell'[[identità che:di Bézout]].

{{S|matematica|crittografia}}

L'algoritmo esteso di Euclide è particolarmente utile quando ''a'' e ''b'' sono [[interi coprimi]]: in questo caso ''x'' è l'[[Aritmetica modulare#Radici primitive|inverso moltiplicativo di ''a'' modulo ''b'']] e ''y'' è l'inverso moltiplicativo di ''b'' modulo ''a''.

In [[aritmetica]] e nella [[Programmazione (informatica)|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 dell'[[identità di Bézout]] ''x'' e ''y'' tali che:

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.

<math>ax + by = \operatorname{MCD}(a, b).</math>

== EsempioStoria ==

L'algoritmo esteso di Euclide è particolarmente utile quando ''a'' e ''b'' sono [[interi coprimi]]: in questo caso ''x'' è l'[[Aritmetica modulare#Radici primitive|inverso moltiplicativo di ''a'' modulo ''b'']] e ''y'' è l'inverso moltiplicativo di ''b'' modulo ''a''.

Le prime documentazioni sull'algoritmo risalgono al [[V secolo a.C.|V]]-[[VI secolo a.C.]], ad opera del [[matematico]] [[Indiani (popolo)|indiano]] [[Aryabhata]]. Fu poi riscoperto più volte indipendentemente, ad esempio dal [[Francia|francese]] [[Claude-Gaspard Bachet de Méziriac|Bachet]] nel [[1621]] e poi da [[Eulero]] intronointorno al [[1731]]<ref>{{Cita libro|autore=André Weil|titolo=Number Theory|anno=2001|editore=Birkhäuser|pp=6-7, 176-77|ISBN=978-0-8176-4571-7}}</ref>.

== Descrizione ==

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.

Dati due numeri interi ''a'' e ''b'', l'[[algoritmo di Euclide]] permette di calcolare le sequenze <math>q_1,\ldots, q_k</math> dei quozienti e <math>r_0,\ldots, r_{k+1}</math> dei resti come segue:

:<math>\begin{align}

Entrambi gli algoritmi trovano 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 (crittografia)|RSA]].

q_1 &=a: b \\

& \,\,\,\vdots \\

q_i &=r_{i-1}: r_i \\

& \,\,\, \vdots

\end{align}</math> <math>\begin{align}

r_0 & =a \\

r_1 & =b \\

& \,\,\,\vdots \\

r_{i+1} & =r_{i-1}-q_{i} r_i \\

& \,\,\, \vdots

\end{align}</math>

La sequenza si arresta quando <math>r_{k+1} = 0</math> e il MCD corrisponde a <math>r_k</math>.

Le prime documentazioni sull'algoritmo risalgono al [[V secolo a.C.|V]]-[[VI secolo a.C.]], ad opera del [[matematico]] [[Indiani (popolo)|indiano]] [[Aryabhata]]. Fu poi riscoperto più volte indipendentemente, ad esempio dal [[Francia|francese]] [[Claude-Gaspard Bachet de Méziriac|Bachet]] nel [[1621]] e poi da [[Eulero]] introno al [[1731]]<ref>{{Cita libro|autore=André Weil|titolo=Number Theory|anno=2001|editore=Birkhäuser|pp=6-7, 176-77|ISBN=978-0-8176-4571-7}}</ref>.

L'algoritmo esteso di Euclide procede in modo simile: si considerano due ulteriori sequenze <math>x_0,\ldots, x_k</math> e <math>y_0,\ldots, y_k</math> tali che:

== Esempio ==

La seguente tabella mostra con un esempio come procede l'algoritmo esteso di Euclide nel caso dei numeri 20 e 7.

<math>\begin{align}

Il calcolo procede con una serie di iterazioni ''i'' da 0 a ''n''. 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.

x_0 &=1 \\

x_1 &=0 \\

& \,\,\,\vdots \\

x_{i+1} &=x_{i-1} - q_i x_i \\

& \,\,\, \vdots

\end{align}</math><math>\begin{align}

y_0 &=0 \\

y_1 &=1 \\

& \,\,\,\vdots \\

y_{i+1} &=y_{i-1} - q_i y_{i} \\

& \,\,\, \vdots

\end{align}</math>

Al termine dell'algoritmo, i coefficienti dell'[[identità di Bézout]] sono <math>x_k</math> e <math>y_k</math>.

I coefficienti di Bézout sono i risultati nelle ultime due colonne della penultima riga. Infatti, è facile verificare l'identità:

=== Esempio ===

<math>ax + by = \operatorname{MCD}(a, b) </math> diventa <math>20 \times (-1) + 7 \times 3 = 1</math>

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 ''nk''. 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 l'identità:che <math>ax + by = \operatorname{MCD}(a, b)</math> poiché <math>20 \times (-1) + 7 \times 3 = 1.</math>

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.

Riga 63 ⟶ 92:

* -1 è l'[[Aritmetica modulare#Radici primitive|inverso moltiplicativo]] di 20 modulo 7, cioè <math>20 \times (-1) \equiv 1\mod 7</math>

* &nbsp;3 è l'inverso moltiplicativo di 7 modulo 20, cioè <math>7 \times 3 \equiv 1\mod 20</math> .

== Applicazioni ==

EntrambiL'algoritmo glidi algoritmiEuclide trovanotrova 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 (crittografia)|RSA]].

== Note ==

<references/>

== Bibliografia ==

* {{cita libro|autore=[[Donald Knuth]]|titolo=Seminumerical Algorithms|anno=1997|editore=Addison-Wesley|volume=2|opera=[[The Art of Computer Programming]]|lingua=en}}

{{Teoria dei numeri}}

{{Algebra}}

{{Portale|matematica|crittografia}}

[[Categoria:Euclide]]

[[Categoria:Algoritmi aritmetici|Euclide]]