Scribd
Importer
98 vues1 page

Algorithme d'Euclide Étendu en Matlab

Le document décrit l'algorithme d'Euclide étendu pour calculer le PGCD de deux nombres et trouver l'inverse d'un nombre modulo un autre si cela existe. Il demande d'écrire une fonction Matlab implémentant cet algorithme et donne des exemples d'applications.

Transféré par

Ñä Đï
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
98 vues1 page

Algorithme d'Euclide Étendu en Matlab

Le document décrit l'algorithme d'Euclide étendu pour calculer le PGCD de deux nombres et trouver l'inverse d'un nombre modulo un autre si cela existe. Il demande d'écrire une fonction Matlab implémentant cet algorithme et donne des exemples d'applications.

Transféré par

Ñä Đï
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

Université de Bejaia UEF 21.

12 Crypto 2022/2023
Faculté de Technologie M2 - ST
Département ATE

TP 4 Algorithme d’Euclide Etendu :

L’Algorithme d’Euclide Etendu permet de calculer de manière itérative le PGCD de 2 nombres et de


trouver l’inverse d’un nombre mod[ ] si il existe

Ecrivez une fonction sous Matlab qui implémente cet algorithme

Algorithme Euclide Etendu :

PGCD (a,b) = a.u + b. v avec, a < b

pseudo code,

Inputs :a, b
Initialisation : r1=b , r2 =a , u1= 0, v1= 1, u2 = 1, v2= 0

tant que r2 ≠ 0 faire

q = r1/r2 (division entière, fonction idivide )


r3 = r1, u3 = u1, v3 = v1
r1= r2 , u1= u2 , v1= v2
r2= r3 – q * r2
u2 = u3 – q * u2
v2 = v3 – q * v2

Outputs :r1, u1 v1

Si PGCD (a,b) = a.u + b. v= 1, on peut dire ( a . u) = 1 [b] , donc u = a-1 [b]

PGCD = r1 , u = u1 et v = v1 .

Application :

- Trouvez le PGCD(973,301) 301 a t-il un inverse [973], 973 a t-il un inverse [301] ?
- Trouvez le PGCD(67,12) 12 a t-il un inverse [67], 67 a t-il un inverse [12] ?

Sous Matlab
int8 (.) entier sur 8 bits
int16 (.) entier sur 16 bits
int32 (.) entier sur 32 bits

Vous devez donc utiliser int16 ou int32

Vous aimerez peut-être aussi