Livre_silo 30 août 2013 16:32 Page 354
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
354
Informatique pour tous
A.6 Arithmétique et cryptographie
A.6.1 Algorithme d’Euclide
Algorithme d’Euclide originel
Soient u, v ∈ N. L’algorithme suivant, dit algorithme d’Euclide, calcule le plus grand diviseur commun (PGCD) de u et v :
A1 Si v = 0 alors la réponse est u.
A2 Faire (u, v) ← (v, u mod v). Retourner en A1.
Écrire une fonction euclide implantant cet algorithme.
Complexité
La complexité de l’algorithme d’Euclide est donnée par le résultat suivant :
éorème (G. Lamé, 1845). Si 0 ⩽ u, v < N , le nombre de divisions dans l’algorithme
d’Euclide appliqué à u et v est au plus ⌈log ϕ (
√
5N )⌉ − 2, où ϕ est le nombre d’or
1+
√
5
2 .
Algorithme d’Euclide étendu
Soient u, v ∈ N. L’algorithme d’Euclide peut être adapté pour calculer, en même temps
que le PGCD de u et v, les coefficients de Bezout. L’algorithme suivant calcule un triplet
(u 1 , u 2 , u 3 ) tel que uu 1 + vu 2 = u 3 = u ∧ v.
B1 (u 1 , u 2 , u 3 ) ← (1, 0, u).
B2 (v 1 , v 2 , v 3 ) ← (0, 1, v).
B3 Si v 3 = 0 alors la réponse est (u 1 , u 2 , u 3 ).
B4 Soit q = ⌊u 3 /v 3 ⌋. Faire
(t 1 , t 2 , t 3 ) ← (u 1 , u 2 , u 3 ) − q(v 1 , v 2 , v 3 )
(u 1 , u 2 , u 3 ) ← (v 1 , v 2 , v 3 )
(v 1 , v 2 , v 3 ) ← (t 1 , t 2 , t 3 )
Retourner en B3.
Écrire une fonction bezout qui réalise cet algorithme.
Démontrer la correction de cette fonction à l’aide d’un invariant.
Application : division modulo m
Soient u, v, m ∈ N
⋆ tels que v ∧ m = 1. On appelle quotient de u par v modulo m tout
entier w tel que 0 ⩽ w < m et u ≡ vw (mod m).
Écrire une fonction calculant le quotient de u par v modulo m.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
354
Informatique pour tous
A.6 Arithmétique et cryptographie
A.6.1 Algorithme d’Euclide
Algorithme d’Euclide originel
Soient u, v ∈ N. L’algorithme suivant, dit algorithme d’Euclide, calcule le plus grand diviseur commun (PGCD) de u et v :
A1 Si v = 0 alors la réponse est u.
A2 Faire (u, v) ← (v, u mod v). Retourner en A1.
Écrire une fonction euclide implantant cet algorithme.
Complexité
La complexité de l’algorithme d’Euclide est donnée par le résultat suivant :
éorème (G. Lamé, 1845). Si 0 ⩽ u, v < N , le nombre de divisions dans l’algorithme
d’Euclide appliqué à u et v est au plus ⌈log ϕ (
√
5N )⌉ − 2, où ϕ est le nombre d’or
1+
√
5
2 .
Algorithme d’Euclide étendu
Soient u, v ∈ N. L’algorithme d’Euclide peut être adapté pour calculer, en même temps
que le PGCD de u et v, les coefficients de Bezout. L’algorithme suivant calcule un triplet
(u 1 , u 2 , u 3 ) tel que uu 1 + vu 2 = u 3 = u ∧ v.
B1 (u 1 , u 2 , u 3 ) ← (1, 0, u).
B2 (v 1 , v 2 , v 3 ) ← (0, 1, v).
B3 Si v 3 = 0 alors la réponse est (u 1 , u 2 , u 3 ).
B4 Soit q = ⌊u 3 /v 3 ⌋. Faire
(t 1 , t 2 , t 3 ) ← (u 1 , u 2 , u 3 ) − q(v 1 , v 2 , v 3 )
(u 1 , u 2 , u 3 ) ← (v 1 , v 2 , v 3 )
(v 1 , v 2 , v 3 ) ← (t 1 , t 2 , t 3 )
Retourner en B3.
Écrire une fonction bezout qui réalise cet algorithme.
Démontrer la correction de cette fonction à l’aide d’un invariant.
Application : division modulo m
Soient u, v, m ∈ N
⋆ tels que v ∧ m = 1. On appelle quotient de u par v modulo m tout
entier w tel que 0 ⩽ w < m et u ≡ vw (mod m).
Écrire une fonction calculant le quotient de u par v modulo m.