Arithmétique pour lacryptographie

11 aout 2015

Chapitre 1

Nombres Premiers etFactorisation

1.1 Nombres premiers

On écrit N = {0, 1, 2, ...} qui est l'ensemble des entiers positifs ou nulset on note Z = {...,−2,−1, 0, 1, 2, ...} qui est l'ensemble des entiers avecles lois usuelles d'addition (+) et de multiplication (notée × ou ·). Onnote N∗ = N − {0} les entiers positifs. De même Z∗ désigne les entiersnon nuls.

Dé�nition 1 Soient a, b ∈ Z avec b 6= 0. On dit que b divise a et onécrit b | a s'il existe c ∈ Z tel que a = b · c (b est diviseur de a et a estmultiple de b).

Dé�nition 2 Soit n ∈ N∗. On dit que n est premier si n > 1 et s'iln'existe pas de factorisation n = a · b avec a et b positifs et a, b < n .Sinon on dit que n est composé.

→ Donc n > 1 est premier si ses seuls diviseurs sont 1 et n .

Théorème 1 Tout entier n > 1 est produit d'entiers premiers :

n =r∏i=1

pi, r ≥ 1 (1.1)

où les pi sont des premiers.

1

Preuve Par induction sur n. Si n = 2 , 2 est premier . Supposons quen > 2 et que chaque entier < n est produit de premiers . Montrons quec'est vrai pour n . Si n est premier, le théorème est vrai . Sinon , n = aboù 1 < a, b < n . Par hypothèse de récurrence a et b sont produits depremiers :a =

∏ri=1 pi et b =

∏sj=1 qj. Donc :

n = (∏i

pi)(∏j

qj)

D'où n est produit de premiers. �.

Théorème 2 (Euclide) Il existe une in�nité de nombres premiers.

Preuve Soit {p1, .., pr} un ensemble �ni de premiers . Soit N = p1...pr+1 qui n'est pas premier. Soit q premier tel que q | N , (Théoreme precedent). Mais , ∀i = 1, .., r, pi - N . Donc q est premier et q 6= pi,∀i. D'où lerésultat �

Proposition 1 Soit N ≥ 1 entier. Alors il existe N entiers composésconsécutifs .

Preuve Prendre :(N+1) !+2 , (N+2) !+3 , ... , (N+1) !+i , ... ,(N+1) !+(N+1).Car ∀i = 2, 3, .., N + 1, on a i | (N + 1)! + i �

Proposition 2 Soit n entier composé . Alors il existe p premier , p | net p <

√n.

Preuve n = ab où 1 < a, b < n . Alors on a : a ou b ≤√n. Supposons

que a√n . Si p est premier et p | a , on a le résultat . �

1.2 Factorisation unique

Proposition 3 (Algorithme de division )Soient a, b ∈ Z, b 6= 0. Alors ils existent q, r ∈ Z tels que a = qb+ r avec|r| < |b|.

2

Preuve Soit q = max{x ∈ Z : x ≤ ab ). On a

q ≤ a

b< q + 1⇒ |a

b− q| < 1.

On pose r = a− qb ∈ Z et on a

|r| = |b(ab− q)| = |b||(a

b− q)| < |b|.

�

Noter qu'on n'a a pas unicité dans cette proposition.

Dé�nition 3 Soient a, b, c ∈ Z.L'entier c est un diviseur commun de a et b si c | a et c | b ; Si enplus : (d | a et d | b) ⇒ d | c, alors on dit que c est un plus grandcommun diviseur de a et b . Dans ce cas , on note c = pgcd(a, b) ouc = PGCD(a, b) ou c = pgcd(a, b) .

Noter que le pgcd est unique si on suppose qu'il doit être positif, conven-tion qu'on va adopter.

Proposition 4 (Algorithme d'Euclide)Si a et b non nuls , le PGCD(a, b) existe et peut etre calculé en unnombre �ni d'étapes par application de l'algorithme de division ci-dessus.

Preuve si b | a alors b est un PGCD(a, b). Sinon , on applique succes-sivement l'algorithme de division : a = q1b+ r1b = q2r1 + r2r1 = q2r2 + r3...

...rm−1 = qm+1rm + rm+1 , m = 3, 4, ...avec qi, ri ∈ Z et |b| > |r1| > |r2| > ... qui est une suite décroissanted'entiers positifs.Donc ∃M tq rM+1 = 0 . Alors rM est le PGCD(a, b). En e�et, en notantpar s(m,n) l'ensemble des diviseurs communs de deux entiers m,n ∈ Z,il est facile de voir que

s(a, b) = s(b, r1) = s(r1, r2) = ... = s(rM , rM+1) = s(rM , 0).

qui est l'ensemble de rM et 0 ; rM inclu . Puisque 0 est divisible parchaque entier, on déduit que rM est le PGCD(a, b). �

3

Remarque 1 On remarque que toute paire (a, b) d'entiers non nuls ad-met deux PGCD : positif et négatif : (±rm), comme signalé auparavent.

On va noter rm > 0, pour PGCD(a, b)

On dit que a et b sont premiers entre eux lorsque PGCD(a, b) = 1 .

Le résultat suivant est appelé théorème de Bezout et est très utile.

Proposition 5 Soit c = PGCD(a, b). Alors ∃x, y ∈ Z, ax+ by = c

Preuve Supposons que b 6= 0 et que b - a (sinon trivial ) .Avec les mêmes notations que la preuve de la proposittion 4 il faut mon-trer qu' ∃x, y ∈ Z tels que ax + by = rM . Par réccurence montrons que∀i = 1, 2, ..,M ri = axi + byi pour certains xi, yi ∈ Z. On a

r2 = a(−q2) + b(1 + q1q2) et r1 = a.1 + b(−q1)

En utilisant l'hypothèse de récurrence :

rm = rm−2 − qmrm−1 = (axm−2 + bym−2)− qm(axm−1 + bym−1)

= a(xm−2 − qmxm−1) + b(ym−2 − qmym−1) �

Lemme 1 (Euclide)Si p premier divisant a1, a2, ..., an, alors ∃i, p | ai .

Preuve Par récurrence sur n. Si n = 1, c'est Ok, et il n' y a rien àdémontrer. Si n = 2, supposons que p | ab et que p - b, et montrons quep | b. Puisque p est premier, pgcd(p, a) = 1. Donc, d'après la relation deBezout, ils existent des entiers x, y tels que ax+py = 1. D'où bax+bpy =b. Et don p | b. Supppsons que le résultat est vrai pour tout entier ≤ n−1et que p |

∏ni=1 ai. Donc p | (

∏n−1i=1 ai)·an. Donc, par le résultat précedent,

on a deux cas : soit p | an, soit p |∏n−1

i=1 ai. Dans le premier cas, on a lerésultat. Dans le second cas, par l'HR, il existe j ≤ n− 1 tel que p | aj.On a donc le résultat. �

Théorème 3 (Factorisation unique )Tout entier positif s'écrit uniquement (en oubliant le rangement des fac-teurs) comme produit de premiers .

4

Preuve D'après le théorème 1, on a à montrer que l'unicité de la factori-sation. On utilise une récurrence sur n. Supposons n =

∏ri=1 pi =

∏sj=1 qi

Si n = 1, c'est trivial. Supposons que n est un entier composé . Par lelemme d'Euclide, on voit que que p1 | qj, j = 1, .., s. Mettons que p1 | q1,et donc p1 = q1. D'où

n

p1= p2...pr = q2...qs < n.

Par HR, on a r = s et ∀i, pi = qi �

Remarque 2 i) Si m ∈ Z∗, alors

(m | ab et PGCD(m, a) = 1)⇒ (m | b)

ii) Si a et b sont des entiers tous les deux non nuls, alors

PGCD(a

PGCD(a, b),

b

PGCD(a, b)) = 1 �

1.3 Application aux équations diophantiennes

lineaires .

On veut trouver toutes les solutions de

r∑i=1

aixi = n (1.2)

pour n, a1, .., ar ∈ Z et les inconnues xi ∈ Z.On traite d'abord le cas particulier à deux inconnues, r = 2, et ensuite

le cas général. On note que pour r = 1, l'équation ax = n ssi a | n.

1.3.1 Cas r = 2

Proposition 6 Soit (a, b) ∈ Z2− (0, 0). On a équivalence entre :(i) ax+ by = n a une solution x, y dans Z(ii) PGCD(a,b)| n.

Preuve (i)⇒(ii) : Simple véri�cation .(ii) ⇒(i) Supposons que PGCD(a, b) = d et donc n = d.t pour unentier t . Donc, par le théorème de Bezout, ∃x0, y0 ∈ Z, ax+by = d ⇒a(x0t) + b(y0t) = n . Par conséquent une solution est x = x0t, y = y0t�

5

Cette proposition donne une solution algorithmique par utilisation dupgcd ; on peut les obtenir toutes :

Proposition 7 Soit (x0, y0) ∈ Z2 solution de ax+ by = n .

Toute solution est de la forme : (∗)

{X = x0 +

ba · t

Y = y0 +ad · t

où d = PGCD(a, b) et t ∈ Z.

Preuve Noter que (*) est une solution . Montrons qu'elle est unique :toute solution est de cette forme.Si ax+ by = n, a

d(x− x0) +bd(y − y0) = 0.

Supposons que b 6= 0 . Alors par application des résutats précédents dela remarque 2 , b

d divise x − x0 : t(b/d) = (x − x0), avec t entier. De larelation (*) on déduit : y− y0 = −(ad)t. Si b = 0 , ax = n et x = n

a = x0et y est quelconque �

1.3.2 Cas général

Pour traiter le cas général de l'eq. (1.2), on a besoin de la dé�ntionsuivante généralisant la notion du PGCD.

Dé�nition 4 soit S ⊆ Z une partie des entiers. Soit c un entier . On dit

que C est un plus grand commun diviseur si

{∀x ∈ S, c | x,∀c′ ∈ Z, (c′ | x,∀x ∈ S) =⇒ c′ | c.

Le lemme suivant donne une méthode de calcul du PGCD en général.

Lemme 2 Supposons que S = a1, a2, .., ar, ... ⊆ Z avec a1 6= 0. Posonsc1 = a1 et ∀i ≥ 2 ci = PGCD(ci−1, ai). Alors PGCD(a1, . . . , ar) =cr , et ∀r ≥ 1, ∃x1, .., xr ∈ Z tels que :

r∑i=1

aixi = cr

Preuve I Par récurrence sur r. On donne l'idée :cn = PGCD(cn−1, an) =⇒ cn | a1, ..., an et cn−1 | a1, ..., an−1.

6

L'HR, cn−1 = PGCD(a1, ..., an−1) permet de conclure.I Si

∑n−1i=1 aix

′i = cn−1, on a ∃x, y ∈ Z tels que :

cn = (n−1∑1

aix′i)x+ any =

n−1∑1

ai(x′i.x) + yan

�

On a pratiquement que le cas pour r = 2, le théorème suivant dans le casgénéral, de même preuve :

Théorème 4∑r

i=1 aixi = n a une solution dans Z⇐⇒ PGCD(a1, .., an)divise n �

Pour obtenir toute les solutions, on utilise le lemme suivant.

Lemme 3 Soit un vecteur a = (a1, ..., ar) ∈ Zr et d = PGCD(a1, ..., ar).Alors ∃C ∈M(Z) matrice carré de taille r × r avec det(C) = ±1 et

a · C = (0, . . . , 0, d)

Preuve (Idée). Par récurrence sur r . Si r = 1, d = |a1| et C =signe(a1). Supposons que r ≥ 2 et que le vecteur (a1, ..., ar−1) 6= 0. Pre-

nons c = PGCD(a1, ..., ar−1). L'HR :

{∃Amatrice (r − 1)(r − 1)

(a1, ..., ar−1) · A = (0, ..., 0, c) ∈ Zr-1.

Soit A∗ =

(A 00 1

), a·A∗ = (0, ..., 0, c, ar) et ∃x, y ∈ Z, cx+ary =

d.

Soit B =

(ard x−cd y

), det(B) = 1 et (c, ar) · B = (0, d). D'où

C = A∗ ·(Ir−2 00 B

)�

Notation : C = (C1, ..., Cr) où Ci est la iéme colonne de C . Avec cesnotations on a le

7

Théorème 5 Soit N ∈ Z. Alors :

(1) x =

x1...xn

∈ Zr est une solution de∑r

i=1 aixi = Nd si et seule-

ment si ∃m1, ...,mr−1

x =r∑i=1

miCi +NCr

(2) L'ensemble des solutions pour N = 0 est un sous groupe de Zr iso-morphe à Zr−1 .

Preuve (1) Posons y = x−N.cr et a · C = (0, ..., d) d'après le Lemme3. On a

∑ri aixi = Nd⇐⇒ a · y = 0

⇐⇒ a · C(C−1.y) = (0, ..., d) · (C−1 · y) = 0

⇐⇒ C−1y = m =

m1...

mr−10

pour certains mi ∈ Z

⇐⇒ y = C ·m = m1 · c1 + ...+mr−1 · cr−1(2) Soit m = (m1, ...,mr−1) ∈ Zr-1. On dé�nit l'application

φ : Zr-1 −→ {solutions}par φ(m) =

∑r−11 mici. Alors φ est un homomorphisme de groupes

surjectif .

Et puisque, detC 6= 0, φ est injectif. �

1.4 Distribution des nombres premiers

Soit P = {p ∈ Z : p premier}. On sait que l'ensemble P est in�ni.Euler a montré que la série

∑p∈P 1/p diverge . (comparer avec

∑∞n=1 1/n

2

qui converge ) . Soit x > 0. On note par

π(x) = {p ∈ P : p ≤ x}.

Si f(x) et g(x) sont des fonctions numériques, on écrit f(x) ∼ g(x)

lorsque limx→∞f(x)g(x) = 1. On cite le théorème suivant, sans preuve, qui

donne le comportement asymptotique de la densité de π.

8

Théorème 6 (Fondamental d'arithmétique )

π(x) ∼ x

log x�

De même, on a le classique

Théorème 7 (Chebychev)

(log 2

4)x

log x<∏

(x) < (6 log 2)x

log x,∀x ≥ 2

.

On veut montrer le

Théorème 8 (Euler) ∑p∈P

1/p diverge.

Lemme 4 Pour N ≥ 2 un entier. On pose q(N) =∏

p≤N,p∈P1

1− 1p

On alim

N−→∞q(N) =∞

.

Preuve On sait que∑∞

n=1 1/n = ∞ et que 11− 1

p

=∑∞

a=01pa

car 1p <

1,∀p ∈ P . Donc q(N) =∏

p≤N(∑∞

a=01pa ). Et donc : q(N) =

∑n∈X

1n où

X est l'ensemble des entiers n tel que n est égal au produit de nombrespremiers ≤ N. Donc {1, ..., N} ⊆ X et q(N) >

∑Nn=1

1n −→N−→∞

∞ �

Corollaire 1 P est in�ni.

Preuve car sinon q(N) qui est un produit �ni, va tendre vers une valeur�nie : contradiction. �

Lemme 5 ∞∑m=1

xm

m= − log(1− x), |x| < 1 �

9

Maintenant on prouve le Théorème d'Euler. On a

log q(N) =∑p≤N

log1

1− 1p

=∑p≤N

∞∑m=1

1

mpm

∑p≤N

1/p+∑p≤N

∞∑m=2

1

mpm

Or ∞∑m=2

1

mpm<

∞∑m=2

1

pm=

1

p(p− 1)<

1

(p− 1)2<

∞∑n=1

1

n2= A

où A est une constante. On a donc∑p≤N

1

p> log(q(N))− A

par le lemme 4. D'où le résultat �

1.5 Fonction φ d'Euler

On introduit la notion de congruence modulo un entier positf, quisera revue au chapitre 2 , tout en gardant des notions éleméntaires, pourmontrer quelques propriétés de la fonction d'Euler φ .

Dé�nition 5 I Soient a, b et m dans Z , m > 0I On dit que a est congru à b modulo m, noté a ≡ b ( mod m) si :m | a− b. Sinon on écrit a � b( mod m).I La relation ≡ sur Z est une relation d'équivalence dont les éle-ments sont appelés classes modulo m.I Si x ∈ Z, sa classe est notée x.I L'ensemble des classes d'équivalence forme un groupe abélien notéZ/mZ = {0, . . . ,m− 1}I Noter que si a ≡ b(mod m ) , c ≡ d(mod) alors : (i) a+ c ≡ b+d(modm) , et (ii) ac ≡ bd (mod m ) .

Preuve En e�et : (i) m | a− b,m | c− d =⇒ m | (a− b)± (c− d)(ii) m | (a− b).c : ac = bc(mod m) et m | (c− d).b : bc = bd(mod m)et par transitivité :

ac ≡ bd (mod m) �

10

Notons Um = {x ∈ Zm/Z : x est premier avec m} le groupe desunités de Z/mZ. Un élément x ∈ Um est appelé une classe premièremodulo m.

Proposition 8 (Um,×) est un groupe pour la multiplication des classesappelé groupe des unités de Z/mZ

Preuve . On a (x,m) = 1 et (y,m) = 1 =⇒ (xy,m) = 1 . D'où lastabilité. On a (x,m) = 1 ⇐⇒ ∃ a, b ∈ Z ax+by =1=⇒ ∃a ∈ Z a.x ≡ 1 (mod m ) et donc a = x−1 �

Proposition 9 Si p est premier , Z/pZ est un corps avec p éléments .

Preuve chaque x 6= 0 dans Z/pZ , admet un inverse d'après proposition, car (x, p) = 1 �

Dé�nition 6 * Un système complet de résidus (SCR) pour Z/mZ estun ensemble de m éléments {a1, ..., an} dans Z tel que

Z/mZ = {a1, ..., an} (1.3)

Autrement dit : ∀i 6= j, ai � aj (mod m ).* Si au lieu de la relation précédente, on a Um = {a1, ..., ar} pour a1, .., ardansZ , on dit que {a1, ..., ar} est un CSR de premiers.

Dé�nition 7 Soit m ∈ Z positif. On note

φ(m) = |{x : 1 ≤ x ≤ m, (m,x) = 1}|

qui est le cardinal d'entiers dans {1, ...,m} qui sont premiers avec m .

Il est facile de véri�er que Si {a1, .., am} est un SCR modulo m, alors∀k ∈ Z, (k,m) = 1, {ka1, .., kam} est aussi un SCR .

Théorème 9 (Euler)Soit a ∈ Z. Si (a,m) = 1 ,

aφ(m) ≡ 1( mod m)

.

11

Preuve soit {a1, .., aφ(m)} un SCR de premiers modulo m. Alors {a ·a1, .., a · aφ(m)} est un SCR de premiers modulo m. D'où

a1...aφ(m) ≡ aa1...aaφ(m) (mod m)

Et donc(aφ(m) − 1) · a1...aφ(m) ≡ 0( mod m).

Puisque(a1...aφ(m),m) = 1,

(car (ai,m) = 1,∀i), on a aφ(m) − 1 ≡ 0( mod m) �

Corollaire 2 (Petit Théorème de Fermat)Soit p ∈ P premier et soit a ∈ Z tel que (a, p) = 1 .Alors

ap−1 ≡ 1 ( mod p)

Preuve On a φ(p) = p− 1. �

Théorème 10 Si (m,m′)=1 , φ(mm′) = φ(m)φ(m′).

On a besoin d'un lemme qui est une version simple du Thm des restesChinois (cf. Chap. suivant).

Lemme 6 Supposons que (m,m′) = 1 . Soit S un SCR modulo m et S'un SCR modulo m′. Alors l'ensemble S ′′ = {am′+a′m : a ∈ S et a′ ∈ S ′}est un SCR modulo mm′.

Preuve Supposons que deux élément de S� soient congrus modulo mm' :

a′1m+ a1m ≡ a′2m+ a2m (mod mm′)

Alorsa1m

′ ≡ a2m′ (mod m),

et puisque (m,m′) = 1 , a1 ≡ a2 (mod m) : contradiction . Donc S"est un SCR mod mm' car | S” |= mm′. �

12

Preuve du Thm 10Le Thm dit que φ est une application multiplicative . Alors avec les no-tations du Lemme 6 , soient m,m′ ∈ Z, (m,m′) = 1 .

φ(mm′) = |S”| = |{am′ + a′m : a ∈ S et a′ ∈ S ′}|On a (am′+a′m,mm′) = 1⇐⇒ (am′+a′m,m) = 1 et (am′+a′m,m′) =1 ⇐⇒ (am′,m) = 1 et (a′m,m′) = 1 ⇐⇒ (a,m) = 1 et (a′,m′) = 1Puisque φ(m) = |S| et φ(m′) = |S ′|, on a alors

φ(mm′) = φ(m)φ(m′) �

Corollaire 3 ∀n ∈ Z positif , φ(n) = n∏

p|n,p∈P(1− 1/p)

Preuve Posons n =∏r

1 paii la factorisation en premiers de n . Donc

d'apres Thm précédent, on a φ(n) =∏r

i φ(paii ) . On a φ(p) = p− 1,∀p ∈

P . Calculons φ(pa).Soit {1, 2, .., pa} un SCR de Z/paZ. Ceux qui ne sont pas premiers avecpa sont les multiples de p : p, 2p, .., pa , au nombre de pa−1 . Donc φ(pa) =pa − pa−1 = pa(1− 1/p). Et ona φ(n) =

∏r1 φ(p

aii ) =

∏r1 p

aii (1− 1/pi) =

n∏r

p|n,p∈P(1− 1/p) �

Corollaire 4 ∀m entier positif, m =∑

d|m φ(d).

Preuve Si m=∏r

1 paii ,∑d|m

φ(d) =∑

(b1,..,br);0≤bk≤ak

r∏i=1

φ(pbii )

=r∏i=1

ai∑bi=0

φ(pbii ) =r∏i

[φ(1) + φ(pi) + ..+ φ(paii )]

=r∏i=1

[1 + (pi − 1) + pi(pi − 1) + ..+ pai−1i (pi − 1)]

=r∏i=1

paii = m �

Dé�nition 8 Une fonction f : Z −→ C est dite multiplicative si ∀m,n ∈Z, (m,n) = 1 =⇒ f(mn) = f(m) · f(n).

13

exemple 1 1) La fonction φ est multiplicative .2) La fonction σ(n) =

∑d|n d somme de diviseurs est multiplicative.

3) La fonction de Möbius est très utile et est multiplicative :

µ(n) =

{0, si ∃x 6= 1, x2 | n.(−1)t, si n = p1 · · · pt produit de t premiers distincts

On a µ(1) = 1 et ∀p ∈ P, µ(p) = −1.

On veut montrer un théorème d'inversion.

Lemme 7 Supposons que f est multiplicative . Alors g dé�nie par g(n) =∑d|n f(d) est aussi multiplicative .

Preuve Supposons que (m,n) = 1. Alors

g(m)g(n) = (∑d|n

f(d))(∑e|n

f(e))

=∑d|n,e|n

f(d)f(e) =∑e,d|n

f(de) =∑c|mn

f(c) = g(mn)

�

Lemme 8 g(n) =∑

d|n µ(d) = 1 si n = 1, 0 sinon.

Preuve µ est multiplicative , le lemme 7 implique que g(n) l'est aussi .On a

∑d|pt µ(d) = µ(1) + µ(p) = 0. D'où , si n 6= 1, g(n) = 0

�

Théorème 11 (Inversion)Si g(n) =

∑d|n f(d) , f(n) =

∑d|n µ(d)g(n/d)

Preuve ∑d|n

µ(d)g(n/d) =∑d|n

µ(d)∑c|n/d

f(c)

=∑d|n

∑c|n/d

µ(d)f(c) =∑d.c|n

µ(d)f(c)

=∑c|n

∑d|n/c

µ(d)f(c) =∑c|n

f(c)∑d|n/c

µ(d)

14

Par le Lemme 8,

=∑c|n

f(c)µ(1) =∑c|n

f(c) = g(n) �

15

Chapitre 2

Le PGCD revisité :Algorithme d'Euclide

2.1 Algorithme d'Euclide

* On cherche ici à donner des algorithmes e�caces de calcul du PGCDde deux entiers. Supposons que u, v ∈ Z positifs avec des factorisationsen nombres premiers :

u =k∏i=1

peii et v =k∏i=1

pfii

Alors

PGCD(u, v) =k∏i=1

pmin{ei,fi}i (2.1)

Mais la méthode de calcul basée sur l'eq. (2.1) utilise la factorisation d'en-tiers, qui n'admet pas d'algorithme connu e�cace.

* La division euclidienne de u par v > 0 donne :

u = av + r, 0 ≤ r < v.

On écrit r := u mod v por désigner le reste de la division euclidiennede u par v. Il est facile de véri�er que

∀d ∈ Z, (d | u et d | v)⇐⇒ (d | v et d | u mod v).

Donc, on en déduit que

PGCD(u, v) = PGCD(v, u mod v).

16

Posons u0 = u et u1 = v et supposons que u1 > 0. Alors, on a u1 >u0 mod u1 ; u2 = u0 mod u1,Donc u1 > u2. De même, u3 = u1 mod u2 , PGCD(u1, u2)=PGCD(u2, u3),etc. On a donc u1 > u2 > ... > uk où uk+1 = 0. Donc PGCD(uk, 0) =uk =⇒ PGCD(u0, u1) = uk. Par conséquent, on déduit l'algorithme ré-cursif suivant :

Algorithme Euclide(u,v)Si u=0, retourner (u)

Sinon retourner (Euclide (v,u mod v))

On a donc sur l'entrée u, v l'algorithme Euclide s'éxécute en O(u) étapes :ce qui est exponentiel en la taille de la représentation binaire du nombreu qui est log(u). On a obtenu ci-dessus la

Proposition 10 L'algorithme Euclide (u, v) avec v > 0 se termine endonnant PGCD(u, v).

On montre ci-dessous qu'une bonne analyse donne un temps d'éxécutionmeilleur en O(log(u) · log(v)).

2.2 Analyse de l'algorithme Euclide

On donne une version itérative de l'algorithme Euclide (u, v).Soient u, v ∈ Z positifs avec v > 0 ; u0 := u, u1 := v

(I)

u0 = a0u1 + u2

u1 = a1u2 + u3... où ai = [ui/ui+1],∀i et un+1 = 0

un−1 = an−1.un

Par conséquent, un = PCGD(u, v). Il faut noter que an−1 ≥ 2 (n 6=1).On va noter par n = E(u, v), dans le processus précédent (I), Le nombrede divisions utilisées et le but et de trouver une "bonne" majoration de n .

* Soit la suite de Fibonacci ,

F0 = 0, F1 = 1 et Fn = Fn−1 + Fn−2 ∀n ≥ 2.

17

Il est facile de voir que Fn =αn−βn√5

ou α = 1+√5

2 et β = 1−√5

2

Lemme 9 Soeint u > v > 0 . Supposons que l'algorithme Euclide (u, v)exécute n étapes sur l'entrée (u, v) . Alors

u ≥ Fn+2 et v ≥ Fn+1

Par récurrence sur n , on montre que dans l'algorithme (I)

u1 ≥ Fn+2 et u0 ≥ Fn+1

Si n = 1 : u0 = a0.u1 > u1 u2 = 0pour u1 = 1, a2 = 0, u0 = 2. Pour ces valeurs u0 ≥ F2 = 3 et u1 ≥ F1 = 1Supposons que ∀i < n, le résultat est vrai .

u0 = a0u1 + u2 et E(u1, u2) = n− 1

=⇒ u1 ≥ Fn+1 et u2 ≥ Fn

=⇒ u0 ≥ u1 + u2 ≥ Fn+2 �

Corollaire 5 Soitu > v > 0 alors :

E(u, v) < C1log(u) + C2 − 2 + C3.u-1,

où

C1 =1

logα' 2.08, C2 =

log√5

logα' 1.67, C3 =

1√5 logα

' 0.93

De même,E(u, v) < C1log(v) + C2 − 1 + C2 − C3v-1

Preuve Supposons que

u = u0 ≥ Fn+2 =αn+2 − βn+2

√5

>αn+2 − 1√

5

=⇒ (n+ 2)log(α) ≤ log(1 + u√5)

On a log(x+1) = log(x)+ log(1+1/x). On sait que log(1+1/x) < 1/x

18

pour x petit .On a donc

(n+ 2)logα ≤ log(u√5) +

1

u√5

n+ 2 ≤ log(u√5)

logα+

1√5u.logα

Doncn ≤ C1logu+ C2 − 2 + C3.u

−1

Donc sin ≥ C1.log(u) + C2 − 2 + C3.u

−1 = K

on a u < Fn−2. En imposant, n = dKe on a u < Fn−2. Par le Lemme 9,on a, si u < Fn+2, alors E(u, v) < n. Mais puisque E(u, v) est un entier,on obtient, E(u, v) < K. �

Supposons que u soit representé en binaire, et puisque on a des divi-sions sur des entiers de longeurs ≤ O(log(u)) , avec un temps O(log(u)2),et en utilisant le corollaire 5, on obtient un temps :

E(u, v) = O(log(u)3).

On peut faire mieux :

Corollaire 6E(u, v) = O(log(u).log(v))

Preuve On observe que l 'algorithme (I) u = u0, v = u1. La divisionde ui = aiui+1 + ui+2 pour avoir ai et ui+2 , prend O(log(ai)log(ui+1))operations (bits) .On a au total ( en O) :

A =∑

0≤i≤n−1log(ai)log(ui+1) ≤ log(v).

n−1∑i=0

log(ai) ≤ log(v)(n+log2(n−1∏i=0

ai))

Orn = O(log(u)) par le Corollaire 5

A ≤ (log(v)).(log(u) + log2(u)) (∗).Donc,

A = O(log(v).log(u)).

19

Noter qu'on montre par récurrence que

n−1∏i=0

ai ≤ u (2.2)

pour obtenir la relation (∗). �

2.3 Algorithme d'Euclide étendu

On a le resultat suivant :

Théorème 12 u, v, c ∈ ZL'equation au+bv = c a une solution en (a,b) si et seulement si PGCD(u, v) |c

Preuve Exercice ; voir section précédente .�

En plus, on a :

Si d = PGCD(u, v), ∃a, b ∈ Z au+ bv = d.

L'objectif est de trouver a, b et le pgcd d. D'après l'algorithme (I) ,on pose les calculs sous la forme :(

u0u1

)=

(a0 11 0

)(u1u2

)=

(a1 11 0

)(u2u3

)· · ·(

un−1un

)=

(an−1 11 0

)(unun+1

)avec

d = un = PGCD(u0, u1) et un+1 = 0

Posons

Mk =

(bk ckdk ek

)=

(a0 11 0

)...

(ak 11 0

)= (Mij)

On a donc

M−1n−1 = (−1).

(en−1 − cn−1−dn−1 bn−1

)20

car det(Mn−1) = (−1)n .

=⇒ en−1.u− cn−1.v = (−1)nd et a = (−1)nen−1 et b = (−1)n+1cn−1.

On obtient l'algorithme suivant.

Algorithme Euclide_étendu(u,v) .

M :=

(1 00 1

); n :=0 .

tant que v6= 0 faire :q=[u/v] (calcul de an)

M :=M.

(q 11 0

)(u,v) :=(v,u-qv)

n :=n+1retourner (d :=u) et (a = (−1)n.M2,2, b = (−1)n+1.M1,2)

Corollaire 7 L'algorithme Euclide_etendu (u, v) est en O(log(u)log(v))opérations bits

Preuve On ab0 ≤ b1 ≤ .... ≤ bn−1 ≤ u

Les bi se calculent par bi+1 = bi.ai+1 + ci pour i ≤ n− 2.On obtient un côut total :∑

0≤i≤n−2((logbi)(logai+1) + (logbi)(logai+1) + logei)

Le Corollaire 5 et la relation (2.2) permettent de terminer la preuve�

2.4 Algorithme d'Euclide et continuants

D'après l'algorithme (I) , on voit que d | ui,∀i = 1, .., n; faisantintervenir des polynomes en les ai.

21

Dé�nition 9 (Continuant)Polynomes en X0, X1, ...

Q0 = 1;Q1 = X0

Qn+1(X0, ..., Xn) = XnQn(X0, ..., Xn−1) +Qn−1(X0, .., Xn−2) , ∀n ≥ 1

On montre alors que si d = PGCD(u, v) et que Euclide(u, v) prend nétapes, alors

∀i ui = d.Qn−i(ai, ..., an−1) (2.3)

Le résultat (2.3) utilise les propriétés des continuants et se fait par récur-rence . On a aussi le résultat suivant :Soient a0, ..., an−1 ∈ Z, a0 ≥ 0, ai ≥ 1 1 ≤ i ≤ n − 1. Soientu = Qn(a0, ..., an−1) et v = Qn−1(a1, ..., an−1). Alors u, v peuvent etrecalculés en O((logu)(logv)) opération en bits.Une fraction continue (�nie) est de la forme :

X0 +1

X1 +1

X2+...+1

Xn

écrite sous la forme[X0, X1, .., Xn]

où les Xi peuvent prendre des valeurs dans Zsoit x ∈ Q. Alors, ∃ a0, a1, ..., an ∈ Z, x = [a0, .., an]

Algorithme FC(x)Donnée : x.

Sortie : (a0, .., an) tq x = [a0, a1, ..., an]i← 0 ; x0 ← x ; a0 ← bx0c

sortir (a0) ;tant que ai 6= 0 faire :

xi+1 ← 1xi−ai ;

i← i+ 1;ai ← bxic;sortir(ai)

�n.

22

Théorème 13 L'algorithme FC(x) donne (a0, a1, ..., an)⇐⇒ x ∈ Q �

Théorème 14 [X0, .., Xn] =Qn+1(X0,..,Xn)Qn(X1,..,Xn)

.

Théorème 15 FC(a/b) = (a0, ..., an−1) ⇐⇒ l'algorithme Euclide(a, b)pour le PGCD(a, b) prend n étapes de divisions.

On constate que la complexité : de FC est presque la même que celle duPGCD qui est O((logu)(logv)).

23