Appunti Informatica

Algortimo di Euclide

Algoritmo di Euclide per il calcolo del Massimo Comune Divisore (MCD) di due interi. Anche in versione estesa. L'articolo è tratto dalla tesi di laurea in "Applicazione delle tecniche di crittografia nella trasmissione ed elaborazione dati" redatta dall'ingegnere Federico Gennari nell'anno accademico 2000/2001.

Algoritmo di Euclide per il calcolo del Massimo Comune Divisore (MCD) di due interi (tempo di lavoro O((lg n)²) operazioni su bit):

INPUT: due interi non negativi a e b (a minore uguale di b)

OUTPUT: MCD di a e b

1)  mentre  ripeti:

poni  r = a mod b; a = b; b = r; (ricordiamo che a mod b restituisce il resto della divisione intera tra a e b)

2)  restituisci a

Algoritmo di Euclide esteso:

INPUT: due interi non negativi a e b,

OUTPUT: d = MCD (a,b) e gli interi x, y tali che ax + by = d.

1)      Se b=0 allora poni d=a, x=1, y=0 e restituisci (d, x, y)

2)      Poni x₂=1, x₁=0, y₁=1.

3)      Mentre b>0 fai i seguenti

          3.1) q=divisione intera di a/b , r= a - qb, x= x₂ - qx₁ , y= y₂ - qy₁ .

          3.2) a =b, b =r, x₂ =x₁ , x₁ =x, y₂ =y₁ , y₁ =y.

4) Poni d= a, x= x2 , y= y2 , e restituisci (d,x,y).

• » Invia tramite EMAIL
• » Versione per la STAMPA
• » Le vostre opinioni

I link correlati all'argomento

• Tesi in tecniche crittografiche
• Appunti di Matematica e Geometria