Scribd
Importer
3 vues3 pages

Algorithm e Euclid e

L'algorithme d'Euclide permet de calculer le plus grand commun diviseur (pgcd) de deux entiers a et b par une série de divisions successives. L'algorithme d'Euclide étendu trouve également un couple de Bézout (x, y) tel que ax + by = pgcd(a, b). De plus, si a et b sont premiers entre eux, l'algorithme permet de déterminer l'inverse modulo b de a.

Transféré par

ayoubchahid059
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
3 vues3 pages

Algorithm e Euclid e

L'algorithme d'Euclide permet de calculer le plus grand commun diviseur (pgcd) de deux entiers a et b par une série de divisions successives. L'algorithme d'Euclide étendu trouve également un couple de Bézout (x, y) tel que ax + by = pgcd(a, b). De plus, si a et b sont premiers entre eux, l'algorithme permet de déterminer l'inverse modulo b de a.

Transféré par

ayoubchahid059
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Algorithme d'Euclide

Soient a, b des entiers tels que 0 < a < b . On pose r 0 = a, r1 = b et par récurrence:

rn−1 = rn qn + rn+1

Avec r n+1
< rn < ⋯ < r1 < r0 . Soit N tel que r N
≠ 0 et r N +1
= 0 . On a

a ∧ b = rN

In [3]: def pgcd(a,b):


# 0 <x,y
if x == 0:
return y
return pgcd(y%x,x)

print(pgcd(3,15))

Algorithme d'Euclide étendu


L'algorithme d'Euclide permet aussi de trouver un couple de Bézout (x, y) tel que ax + by = a ∧ b . Généralement, pour n on cherche
xn , yn ∈ Z tel que

rn xn + rn+1 yn = a ∧ b

La calcul de x et y se fait par récursivité du fait que


n n

a ∧ b = rn xn + rn+1 yn = rn−1 yn + (xn − qn yn )rn

Donc on peut choisir

xn−1 = yn , yn−1 = xn − qn yn

Avec x N = 1 et Avec y N = 0 .
In [30]: def bezout(a,b):
# On se rammene a a,b positifs on multipliant si necessaire x et y par -+1
sa = 1
sb = 1
if a < 0:
sa = -1
a = -a
if b <0:
sb = -1
b = -b
if b==0:
return a,1,0 # pgcd(a,b) , x, y :ax+by = pgcd(a,b)
r, u,v = bezout(b,a%b)
return r, sa*v, (u- (a//b)*v)*sb

print(bezout(17,-34));

(17, 1, 0)

Inverse modulo b de a
Si a et b sont premiers entre eux, alors il existe x, y ∈ Z tel que ax + by = 1 . Donc

ax ≡ 1 mod b

x mod b est appelé inverse modulo b de a,

In [ ]:

In [21]: def inverseMod(a,b):


r, x,y = bezout(a,b)
return x%b

print(inverseMod(17,13))

10

In [23]: (10*17-1)/13
13.0
Out[23]:

Vous aimerez peut-être aussi