Jol Riou

MAO CALCUL FORMEL, COURS DE M1

Jol Riou
E-mail : [email protected]

$Id: cours. tex,v 1. 3 2012-09-22 13: 51: 17 cvs Exp $

MAO CALCUL FORMEL, COURS DE M1

Jol Riou

TABLE DES MATIRES

Bibliographie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1. Ordres de grandeur, cot. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1. Dfinitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Quelques rgles de calcul. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Exemples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1. Polynmes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.2. Suites rcurrentes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4. Cots de quelques algorithmes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.1. Exponentiation rapide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.2. Multiplication rapide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.3. Suite de Fibonacci. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11
11
11
12
12
12
13
13
14
15

2. Arithmtique, algorithme dEuclide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1. Rappels darithmtique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1. Anneaux, idaux, pgcd, ppcm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2. Restes chinois. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.3. Anneaux principaux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.4. Anneaux euclidiens. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Algorithme dEuclide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1. Calcul du pgcd. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2. Dtermination de coefficients de Bzout. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3. Cot en temps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17
17
17
18
19
20
20
20
21
21

3. Corps finis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1. Premires observations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Terminologie gnrale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1. Extensions, degrs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2. Corps de rupture. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3. Composes de deux extensions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25
25
26
26
26
28

TABLE DES MATIRES

3.2.4. Polynmes scinds, corps de dcomposition. . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.5. Polynmes sparables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3. Existence et unicit des corps finis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4. Polynmes irrductibles sur un corps fini. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28
29
30
30

4. Factorisation dans Fq [X]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1. Rduction au cas des polynmes sans facteur carr. . . . . . . . . . . . . . . . . . . . . . .
4.1.1. Polynmes sans facteurs carrs, polynmes sparables. . . . . . . . . . . . . . .
4.1.2. Algorithme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Algorithme de Berlekamp. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1. Dtermination du nombre de facteurs irrductibles. . . . . . . . . . . . . . . . . .
4.2.2. Dtermination dun facteur non trivial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35
35
35
36
37
37
38

5. Rsultants. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1. Dfinitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2. Formules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3. Proprits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4. Exemples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1. Courbes paramtres : cercle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.2. Courbes paramtres : cardiode. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.3. Intersection de deux courbes planes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39
39
40
42
43
43
44
44

6. Lemme de Hensel, borne de Mignotte, factorisation dans Z[X] . . . . . .

6.1. Lemme de Hensel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.1. Rsolution dquations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.2. Factorisation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2. Borne de Mignotte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3. Factorisation dans Z[X] et Q[X]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45
45
45
47
47
49

7. Rsidus quadratiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1. Symbole de Legendre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2. Symbole de Jacobi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3. Dmonstration de la loi de rciprocit quadratique. . . . . . . . . . . . . . . . . . . . . . .
7.3.1. Zolotarev. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3.2. Sommes de Gauss. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3.3. Rsultants. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4. Test de primalit de Solovay-Strassen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51
51
52
54
54
55
57
58

8. Factorisation dentiers, cryptosystme RSA. . . . . . . . . . . . . . . . . . . . . . . . . . . .

8.1. Algorithme de Pollard. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2. Cryptographie clef publique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2.1. Principe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2.2. Le cryptosystme RSA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2.3. Signature. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61
61
63
63
63
64

9. Transforme de Fourier discrte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

9.1. Racines de lunit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

TABLE DES MATIRES

9.2. Transforme de Fourier discrte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9.3. Transforme de Fourier rapide (FFT). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.4. Multiplication rapide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.5. Un algorithme de factorisation dentiers (Pollard, Strassen). . . . . . . . . . . . . .
9.5.1. Principe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.5.2. Produit multiple de polynmes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.5.3. valuations multiples dun polynme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.5.4. Division euclidienne. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.5.4.1. Inversion modulo X k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.5.4.2. Division euclidienne rapide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68
69
70
73
73
73
74
74
74
75

10. Mthodes dinterpolation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10.1. Interpolation de Lagrange. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.1.1. Vandermonde. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.1.2. Interpolation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.1.3. Majoration de lerreur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.1.4. Polynmes de Tchebychev. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2. Diffrences finies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2.1. Interpolation par diffrences finies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2.2. Lien avec la formule de Taylor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.3. Interpolation de Hermite. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.3.1. Principe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.3.2. Gnralisation de lalgorithme dEuclide tendu. . . . . . . . . . . . . . . . . . . .

77
77
77
78
79
79
81
81
81
83
83
83

BIBLIOGRAPHIE

[1] Maurice Mignotte. Mathmatiques pour le calcul formel. PUF.

[2] Bernadette Perrin-Riou. Algbre, arithmtique et Maple. Cassini.
[3] Thomas Cormen, Charles Leiserson et Ronald Rivest. Introduction lalgorithmique. Dunod.
[4] Joachim von zur Gather, Jrgen Gerhard. Modern Computer Algebra. Cambridge.

CHAPITRE 1
ORDRES DE GRANDEUR, COT

Buts :
comparer le comportement asymptotique de suites ;
fournir un outil de mesure du cot des algorithmes.
Les lettres u, v, w, etc. dsignent des suites relles, autrement dit des applications
N R.
1.1. Dfinitions
Dfinition 1.1.
si l R, on dit que u tend vers l (not u l, ou

lim un = l) si pour tout

n+

> 0, il existe un entier N tel que pour tout n N , |un l| ;

u est un grand O de v (not u = O(v)), sous-entendu quand la variable n tend
vers +, sil existe k > 0 tel qu partir dun certain rang, on ait |un | k|vn | ;
u est un petit o de v (not u = o(v)), si pour tout > 0, il existe un entier N
tel que pour tout n N , on ait |un | |vn |.
u est quivalent v (not u v), si u v = o(v).
Si v ne sannule pas ( partir dun certain rang...), on a les critres suivantes :
u = O(v) si et seulement si la suite u/v est borne (1) ;
u = o(v) si et seulement si la suite u/v tend vers 0
u v si et seulement si la suite u/v tend vers 1.
1.2. Quelques rgles de calcul

si u = o(v) ou u v, alors u = O(v).

u u;
u v quivaut v u.
si u v et v w, alors u w.

1. Autrement dit, on peut supprimer partir dun certain rang dans la dfinition. Cependant,
considrer lassertion n2 = O(n(n 1)).

12

CHAPITRE 1. ORDRES DE GRANDEUR, COT

si
si
si
si
si

u = O(w) et v = O(w), alors u + v = O(w).

u = O(v) et v = O(w), alors u = O(w).
u = O(v) et u0 = O(v 0 ), alors uu0 = O(vv 0 ).
u v, alors w = O(u) quivaut w = O(v) ;
u v, alors w = o(u) quivaut w = o(v).

1.3. Exemples
1.3.1. Polynmes.
Proposition 1.2. Soit P R[X] = ad X d + + a0 un polynme de degr d
(ainsi ad 6= 0). Alors P (n) ad nd . En particulier, P (n) = O(nd ).
Proposition 1.3. Soit P R[X]. Il existe un unique polynme Q R[X] tel
que Q(1)
Pn= 0 et que Q(X + 1) Q(X) = P (X + 1). Ainsi, pour tout n N, on a
Q(n) = k=0 P (k). Si P est non nul, on a deg Q = deg P + 1.
Pn
Corollaire 1.4. Pour tout entier k, k=0 nk = O(nk+1 ).
Corollaire 1.5. Soit k N (2) . On suppose que un = O(nk ). Alors,
n
X

ui = O(nk+1 ) .

i=0

1.3.2. Suites rcurrentes. Soit u une suite termes strictement positifs.

sil existe une constante > 0 telle que un+1 un (autrement dit un+1 =
O(un )), alors un = O(n ).
sil existe k N tel que un+1 = un + O(nk ), alors un = O(nk+1 ).
si un ud n e + O(1), alors un = O(log2 n).
2

si un 2ud n e + O(n), alors un = O(n log2 n).

2

Dmonstration. Cas o un ud n e + O(1).

2
Il existe > 0 tel que pour tout n, un ud n e + . Par rcurrence sur d N, on
2

montre que pour tout 2d + 1 n 2d+1 , on a un u1 + (d + 1). Ainsi, pour tout

n 2, on a un u1 + (1 + log2 n), ce qui permet de conclure que un = O(log2 n).
Cas o un 2ud n e + O(n).
2
Il existe > 0 tel que pour tout n, un 2ud n e + n. On choisit un nombre rel M
2

suprieur u1 et . Par rcurrence sur d N, on montre pour tout 2d +1 n 2d+1 ,

on a un M ad o la suite ad est dfinie par a0 = 4 et la relation de rcurrence
ad = 2ad1 + 2d+1 . On montre que ad = (2 + d) 2d+1 (3) . Par suite, comme d log2 n,
on obtient que un 2M (2 + log2 n) n pour tout n 1, do un = O(n log2 n).

2. Le rsultat vaut aussi si on remplace lexposant entier k par un nombre rel > 1.
3. Pour retrouver ce rsultat, considrer la suite bd = a2dd et montrer quelle vrifie la relation de
rcurrence bd = bd1 + 2.

1.4. COTS DE QUELQUES ALGORITHMES

13

1.4. Cots de quelques algorithmes

1.4.1. Exponentiation rapide. Dans un anneau A, on veut calculer an , o
a A et n N.
Lalgorihme trivial consiste faire une boucle :
def expo_lente(a,n):
x = 1
for i in range(n):
x*=a
return x
Si on considre la multiplication comme une opration lmentaire, le cot (en
temps) de cet algorithme est O(n). Le cot en espace est O(1).
Lalgorithme dexponentiation rapide sappuie sur lgalit a2n = an an . Pour
calculer an avec n 1, on distingue deux cas :
si n est pair, on dtermine lentier m tel que n = 2m, on calcule b = am et on
renvoie b2 ;
si n est impair, on dtermine lentier m tel que n = 2m + 1, on calcule b = am
et on renvoie ab2 .
Ainsi dcrit, il est naturel dimplmenter cet algorithme par une fonction rcursive :
def exponentiation_rapide_rec(a,n):
if n == 0:
return 1
if n == 1:
return a
y = expo(a,n//2);
if n%2 == 0:
return y*y
else:
return a*y*y
Le nombre dappels rcursifs la fonction exponentiation_rapide_rec est en
O(log2 n). Le cot en temps est donc aussi en O(log2 n).
Les appels rcursifs cette fonction sorganisent en un arbre de profondeur
O(log2 n). Le cot en mmoire nest pas constant. Il peut tre intressant de rcrire
la fonction sous forme dune boucle de faon conserver un cot en O(log2 n) tout
en ayant un cot en espace en O(1) :
def expo_rapide_iteratif(a,n):
r=1;
N=n;
A=a;
while(N>0):
if N%2 == 1:
r=r*A
A=A*A;
N=N//2;

14

CHAPITRE 1. ORDRES DE GRANDEUR, COT

return r
Le calcul termine puisqu chaque passage dans la boucle, N dcroit strictement ;
plus prcisment, le nombre de passage dans la boucle est en O(log2 n). Pour montrer
que cette fonction fait bien ce quelle doit, considrer linvariant de boucle an =
r AN . Le cot en espace est constant et le cot en temps est en O(log2 n).
Remarque 1.6. On a suppos que le cot dune multiplication tait constant.
Si on travaille dans un anneau Z/2n Z, cest le cas et les oprations sur les entiers
ralises par les processeurs rentrent essentiellement dans ce cadre.
1.4.2. Multiplication rapide. Soit n un entier naturel. Un entier naturel n
bits est un entier compris entre 0 et 2n 1 : on reprsenteP
un entier par le n-uplet
n1
(bn1 , . . . , b0 ) dentiers valant 0 ou 1 tel que cet entier soit i=0 bi 2i . On cherche
calculer le produit de deux entiers n bits (le rsultat a au plus 2n bits).
Thorme 1.7 (Karatsuba). On peut multiplier deux entiers n bits en
O(nlog2 3 ) (4) oprations lmentaires sur les bits.
Soit m un entier. Des entiers 2m bits x et y peuvent tre reprsents sous la
forme x = a2m + b et y = c2m + d o a, b, c, d sont des entiers naturels au plus m
bits. On a
xy = ac 22m + (ad + bc) 2m + bd .
Un algorithme possible pour faire la multiplication consiste calculer les quatre produits ac, ad, bc et bd dentiers m chiffres, puis faire les oprations faciles (dcalage
et additions) pour obtenir le rsultat xy.
Notons ck le cot en oprations par bits de la multiplication de deux entiers
2k bits. En appliquant rcursivement la mthode ci-dessus, on obtient une relation
de rcurrence ck+1 = 4ck + O(2k ). Le quotient dk = 4ckk vrifie une relation dk+1 =
dk + O( 21k ) dont on dduit que la suite dk converge, ainsi ck = O(4k ). Finalement, on
peut en conclure que lon peut faire le produit dentiers n bits en O(n2 ) oprations.
Lalgorithme de Karatsuba sappuie sur le fait que lon peut dterminer ac, ad + bc
et bd en faisant quelques additions et surtout trois multiplications au lieu de quatre.
En effet, on peut N = (a + b) (c + d), ac et bd, et en dduire ad + bc puisquon a
ad + bc = N ac bd. Notons c0k le cot de la multiplication de deux entiers 2k bits
pour cette mthode. On a cette fois-ci ck+1 = 3ck +O(2k ), dont on dduit ck = O(3k ).
Si n est un entier naturel non nul, on peut considrer la plus petite puissance de 2
2k qui lui est suprieure, on a alors k log2 n + 1. Comme 3log2 n = nlog2 3 , on peut
multiplier deux entiers n bits en O(nlog2 3 ) (et donc O(n1.585 )).
Le cot en espace est en O(n). En effet, notons Mk le cot en espace de la multiplication des entiers 2k bits. On obtient
Mk+1 = O(2k ) + Mk .
En effet, pour faire le calcul pour des entiers 2k+1 , on a besoin de stocker quelques
entiers au plus 2k+2 bits pour les rsultats des calculs intermdiaires, ceci donne
4. log2 3 ' 1.58496 . . .

1.4. COTS DE QUELQUES ALGORITHMES

15

une contribution en O(2k ). Puis, on doit faire trois appels rcursifs pour faire des
multiplications sur des entiers 2k chiffres. Le calcul de la premire multiplication
ncessite un surcot de Mk , la deuxime et la troisime multiplication aussi, mais on
peut librer la mmoire utilise par la premire avant de lancer la deuxime, etc. Le
cot en mmoire des trois multiplications de chiffres 2k bits est Mk , et pas 3Mk .
Ainsi, Mk est un grand O de la somme partielle de la srie des 2k , do Mk = O(2k ).
On en dduit que lalgorithme de Karatsuba permet de faire la multiplication des
entiers n bits avec un cot en espace de O(n).
Remarque 1.8. Il est en fait possible de multiplier deux entiers n bits en
O(n ln n ln ln n) oprations lmentaires
1.4.3. Suite de Fibonacci. La suite de Fibonacci Fn est dfinie par les galits
F0 = 0, F1 = 1 et la relation de rcurrence Fn+2 = Fn + Fn+1 .
Proposition 1.9. Pour tout entier naturel n, on a
 n  n
1+ 5
12 5
2

.
Fn =
5

En particulier, Fn 15 n o = 1+2 5 est le nombre dor.

Plusieurs mthodes de calcul des entiers Fn sont possibles. En voici une stupide :
def fibonacci(n):
if n<=1:
return n
return fibonacci(n-2)+fibonacci(n-1)
Si on considre laddition entire comme une opration lmentaire, le cot en
temps est en O(n ), ce qui est extrmement mauvais.
Une autre mthode consiste faire une boucle pour calculer le couple (Fk , Fk+1 )
pour k de 0 n 1 :
def fibonacci2(n):
a = 0;b=1
for i in range(n):
c=a
a=b
b=a+c
return a
Le cot en temps de fibonacci2 est en O(n).
On peut faire mieux. Rappelons que si on a une suite dfinie par une quation de
rcurrence linaire de la forme un+2 = aun + bun+1 , on peut introduire la matrice


0 1
M=
.
a b
La relation de rcurrence se rcrit :




un+1
un
=M
un+2
un+1

16

CHAPITRE 1. ORDRES DE GRANDEUR, COT

Par consquent,





un
u0
= Mn
,
un+1
u1
ainsi, le calcul de un nest pas plus compliqu que celui de M n . Lalgorithme dexponentiation rapide sapplique lexponentiation de matrices. On obtient ainsi un
algorithme ayant un cot en O(log2 n). Une implmentation possible en Sage est la
suivante :
def fibonacci3(n):
m = matrix(2,2,[0,1,1,1])**n
return m[0,1]

CHAPITRE 2
ARITHMTIQUE, ALGORITHME DEUCLIDE

2.1. Rappels darithmtique

2.1.1. Anneaux, idaux, pgcd, ppcm.
Dfinition 2.1. Soit A un anneau. Un idal I de A est un sous-groupe de (A, +)
tel que pour tout a A et x I, ax I.
Remarque 2.2. Si I est un idal de A, le groupe ablien A/I est naturellement
muni dune structure danneau telle que le morphisme de projection A A/I soit
un morphisme danneaux. Tout idal de A/I scrit de manire unique sous la forme
J/I o J est un idal de A contenant I.
Dfinition 2.3. Si a1 , . . . , an sont des lments de A, lidal engendr par ces
lments, not (a1 , . . . , an ), est lensemble des combinaisons linaires ( coefficients
dans A) de ces lments. Un idal pouvant scrire sous la forme (a) pour un certain
a A est un idal principal.
Dfinition 2.4. Soit A un anneau. Soit a A, soit b A. On dit que a divise b
(et on le note a|b), ou encore que b est multiple de a, sil existe x A tel que b = ax,
cest--dire que b (a), ou que (b) (a), ou encore que la classe b de b dans A/(a)
est nulle.
Dfinition 2.5. Soit A un anneau. On dit que A est intgre si A est non nul (i.e
1A 6= 0A ) et que si (x, y) A2 sont tels que xy = 0, alors x = 0 ou y = 0. Un idal p
de A est premier si lanneau quotient A/p est intgre. Un idal m de A est maximal
si et seulement si m 6= A et que m est maximal pour cette proprit, ceci quivaut
demander que A/m soit un corps.
Proposition 2.6. Soit A un anneau intgre. Soit a A, soit b A, si (a) = (b),
alors il existe un lment u A tel que b = ua.
Ainsi, dans un anneau intgre, se donner un idal principal revient se donner une
classe dquivalence dlments de A pour la relation dquivalence qui identifie a et
b sil existe un inversible u tel que b = ua.

18

CHAPITRE 2. ARITHMTIQUE, ALGORITHME DEUCLIDE

Dfinition 2.7. Soit A un anneau intgre. Soit a A, soit b A. Le pgcd de a et

de b est un lment y (parfois not a b) de A divisant a et b et tel que tout lment
divisant a et b divise aussi y. Sil existe le pgcd est dfini un facteur inversible prs.
Le ppcm de a et de b est un lment y (parfois not a b) de A multiple de a et de b
tel que tout multiple de a et de b soit aussi un multiple de y (1) . Sil existe, le ppcm
est aussi dfini facteur inversible prs.
Proposition 2.8. Soit A un anneau intgre. Soit a A, soit b A. Le ppcm de
a et b existe si et seulement si lidal (a) (b) est principal ; le ppcm est un gnrateur
de cet idal.
Proposition 2.9. Soit A un anneau intgre. Soit a A, soit b A. Si lidal
(a, b) est principal ; le pgcd de a et b existe et est un gnrateur de (a, b).
Soit x A. Si x divise a et b, alors x divise tous les lments de lidal (a, b). Par
consquent, x divise a et b quivaut (a, b) (x). Supposons que y A soit tel que
(y) = (a, b). Daprs ce qui prcde, y divise a et b et tout lment x qui divise a et b
est tel que (y) (x), donc x divise y, ce qui montre que y est le pgcd de a et de b.
Dfinition 2.10. Soit A un anneau intgre. Soit x un lment non nul et non
inversible de A. On dit que x est irrductible si ds lors que lon a x = ab avec
(a, b) A2 , alors a ou b est inversible. On dit que x est rductible sil nest pas
irrductible, savoir que lon peut crire x comme produit de deux lments non
inversibles.
2.1.2. Restes chinois.
Dfinition 2.11. Soit A un anneau. On dit de deux lments a et b quils sont
trangers si (a, b) = 1.
Remarque 2.12. Dans un anneau A, a et b sont trangers si et seulement si la
classe de a dans A/(b) est inversible.
Proposition 2.13. Soit A un anneau. Soit (a, b) A2 . On suppose que a et b
sont trangers. Alors, (a) (b) = (ab), et le morphisme vident danneaux
: A/(ab) A/(a) A/(b)
est un isomorphisme.
On choisit une relation au + bv = 1. On a videmment (ab) (a) (b). Soit x
(a)(b). On peut crire x = ax0 , x = bx00 , do x = (au+bv)x = abux00 +abvx0 (ab).
Le morphisme danneaux considr est donc injectif.
Considrons lgalit au + bv = 1. On en dduit les congruences au 0[a] et
au 1[b]. Par consquent, ([au]) = (0, 1). De mme, ([bv]) = (1, 0). Si x et y
sont deux lments de A, il vient ([xbv + yau]) = ([x], [y]), ce qui montre que est
surjectif.
1. On peut tendre la dfinition du pgcd et du ppcm donne ici pour deux lments une famille
dlments de A.

2.1. RAPPELS DARITHMTIQUE

19

Thorme 2.14. Soit A un anneau. Soit n 1. Soit (a1 , . . . , an ) un n-uplet

dlments deux--deux trangers. Le morphisme danneaux
: A/(a1 . . . an ) A/(a1 ) A/(an )
est un isomorphisme.
On procde par rcurrence sur n. Si n 3, on peut appliquer le thorme au cran
n 1 pour les lments a1 , . . . , an1 et au cran 2 pour le couple a1 . . . an1 , an .
Lemme 2.15 (Gau). Soit A un anneau. On se donne des lments (a, b, c) de
A tels que a|bc et que a et b soient trangers. Alors, a|c.
Comme a et b sont trangers, limage b de b dans A/(a) est inversible. Par hypothse, bc = 0 dans A/(a). On en dduit que c = 0 dans A/(a), ce qui signifie que a
divise c.
2.1.3. Anneaux principaux.
Dfinition 2.16. Un anneau principal est un anneau intgre dont tout idal est
principal.
Dans un anneau principal, les pgcd et ppcm existent toujours.
Proposition 2.17. Lanneau des entiers Z est principal. Pour tout corps k, lanneau des polynmes k[X] est principal.
Ceci sera une consquence de la proposition 2.22.
Thorme 2.18 (Bzout). Soit A un anneau principal. Soit a A, soit b A.
Il existe (u, v) A2 tels que au + bv = a b.
Dfinition 2.19. Soit A un anneau principal. On dit deux deux lments a et
b quils sont premiers entre eux si a b = 1. Daprs le thorme de Bzout, ceci
quivaut dire quils sont trangers.
Proposition 2.20. Soit A un anneau principal. Soit x un lment non nul de A.
Alors x est irrductible si et seulement sil engendre un idal premier. Par ailleurs,
tout idal premier non nul de A est maximal.
Supposons (x) premier. Montrons que x est irrductible. Donnons-nous une criture
x = ab avec (a, b) A2 . En particulier, ab (x), donc a ou b appartient (x). On
veut montrer que a ou b est inversible. Par symtrie des rles, on peut supposer que
a (x), il existe c A tel que a = cx, do x = bcx. Comme x est non nul, il vient
bc = 1, par consquent b est inversible (2) .
Supposons maintenant que x est irrductible. Montrons que (x) est un idal maximal (donc en particulier un idal premier). Supposons donc (x) I avec I 6= A. On
peut crire I = (y) avec y A. Donc, y|x, il existe z A tel que x = yz. Comme x
est irrductible et que y est non inversible, z est inversible, do I = (y) = (x), lidal
(x) est maximal.
2. On notera que ce sens dimplication vaut dans un anneau intgre quelconque.

20

CHAPITRE 2. ARITHMTIQUE, ALGORITHME DEUCLIDE

2.1.4. Anneaux euclidiens.

Dfinition 2.21. Un anneau euclidien est un anneau intgre A muni dune fonction (appele jauge ) v : A {0} N (on la prolonge A en posant v(0) = )
telle que pour tout (a, b) A2 tels que b 6= 0, il existe (q, r) A2 tels que a = bq + r
et v(r) < v(b) (3) .
Lanneau des entiers est euclidien : prendre pour v la valeur absolue. Lanneau des
polynmes k[X] sur un corps : prendre pour v le degr des polynmes.
La proposition ci-dessous est un cas particulier du rsultat gnral :
Proposition 2.22. Un anneau euclidien est principal.
Soit I un idal dun anneau euclidien (A, v). Montrons que I est principal. On peut
supposer I non nul. Lensemble des v(x) pour x I {0} est un sous-ensemble non
vide de N, il admet un plus petit lment v(b) avec b I. Lidal I est engendr
par b. En effet, soit x I, on peut faire la division euclidienne de x par b, ce qui
fournit des lments q et r tels que x = bq + r avec v(r) < v(b). Comme r I, la
proprit de minimalit de v(b) interdit que r 6= 0. Donc r = 0, do x = bq, ce qui
achve de montrer linclusion I (b) ; lautre inclusion tant vidente, on a dmontr
la proposition.
Proposition 2.23. Le cot en oprations arithmtiques (additions, multiplications, divisions) de la division euclidienne dun polynme A par un polynme B est
en O((deg A+1)(deg B+1)) soit O(deg Adeg B) si les polynmes sont non constants.
Plus prcisment, si deg A > deg B > 0, le cot est un O(deg B (deg A deg B)).
Notons a = deg A et b = deg B, et supposons pour simplifier que a > b. Si on note
Q le quotient de la division euclidienne, on a : Q = qab X ab + . . . . Lalgorithme
consiste dterminer successivement qab , qab1 , . . . , q0 de la faon suivante.
On dfinit une suite de polynmes Ri par : R0 = A. Pour i allant de 0 jusqu
a b, on note qabi le quotient du coefficient de X ai dans Ri par celui de X b dans
B. On calcule la diffrence Ri+1 := Ri qabi X abi B. la sortie de la boucle, les
coefficients de Q ont tous t dtermins et le reste R de la division euclidienne est
Rab+1 .
PEn effet, on dispose dun invariant de boucle suivant : au dbut de ltape i, A =
i1
abk
B + Ri et deg Ri a i .
k=0 qabk X
chaque tape de la boucle, on fait O(b) oprations. Comme on passe a b + 1
fois dans la boucle, on obtient un cot en O(b(a b)) ds lors que a > b.

2.2. Algorithme dEuclide

2.2.1. Calcul du pgcd.
3. Dterminer un tel couple (q, r) sappelle faire la division euclidienne de a par b .

2.2. ALGORITHME DEUCLIDE

21

Proposition 2.24. Soit A un anneau euclidien, de jauge v. Soit (a, b) A2 . On

suppose que b 6= 0. On effectue la division euclidienne de a par b : on dtermine
(q, r) A2 tels que a = bq + r et v(r) < v(b). Alors, a b = b r.
Il suffit de montrer lgalit des idaux (a, b) = (a bq, b).
Lalgorithme dEuclide permet de dterminer le pgcd de deux lments a et b dans
un anneau euclidien A. On distingue plusieurs cas :
(i) si b est nul, on renvoie a ;
(ii) sinon, on calcule le reste r de la division euclidienne de a par b, on remplace
(a, b) par (b, r) et on recommence.
Si les lments a et b vrifient v(b) < v(a), on va conserver cette proprit lors des
itrations suivantes. La valeur v(a) va dcrotre strictement chaque itration, ce qui
assure que lalgorithme termine et quil renvoie le bon rsultat daprs la proposition
ci-dessus.
Si on a v(b) v(a), on aura v(b) < v(a) lors de litration suivante, et le raisonnement prcdent sapplique. Ainsi, lalgorithme dEuclide termine toujours et renvoie
un rsultat correct.
2.2.2. Dtermination de coefficients de Bzout. Notons A et B les lments
dont on veut dterminer le pgcd ainsi que des coefficients de Bzout u et v tels que
Au + Bv = A B. Pour dterminer ces coefficients de Bzout, il suffit de garder en
mmoire une reprsentation de a et de b sous la forme dune combinaison linaire de
A et de B. En effet, la terminaison de lalgorithme, le pgcd renvoy est a, si on sait
crire a comme combinaison linaire de A et de B, on peut renvoyer les coefficients
de Bzout.
On peut stocker les coefficients des combinaisons linaires sont la forme dune
matrice M telle que




a
A
=M
.
b
B
def euclide_etendu(A,B):
a=A
b=B
M=matrix(2,2,[1,0,0,1]);
while b<>0:
D=a//b
r=a%b
a=b
b=r
M=matrix(2,2,[0,1,1,-D])*M
return (a,M[0,0],M[0,1])
2.2.3. Cot en temps. On va estimer le nombre dtapes utilises par lalgorithme dEuclide pour dterminer un pgcd.

22

CHAPITRE 2. ARITHMTIQUE, ALGORITHME DEUCLIDE

Thorme 2.25 (Lam). Soit (a, b) un couple dentiers naturels tel que a > b.
Soit n un entier naturel non nul. Si lalgorithme dEuclide pour le calcul du pgcd de
(a, b) ncessite n tapes, alors a Fn+2 et b Fn+1 . En outre, lalgorithme dEuclide
fait le calcul du pgcd de Fn+2 et de Fn+1 en exactement n tapes.
On procde par rcurrence sur n. Dire que le calcul ncessite zro tape signifie
que b = 0 (et a 1), laffirmation est donc fausse pour n = 0. Si n = 1, on a
bien videmment b 1 et donc a 2. Supposons que n 2 et que le rsultat est
connu pour n 1. On applique la premire tape de lalgorithme dEuclide (a, b),
on obtient ainsi un nouveau couple (b, r) (avec r le reste de la division euclidienne
de a par b), et le calcul de lalgorithme dEuclide pour (b, r) ncessite n 1 tapes.
Lhypothse de rcurrence montre que b Fn+1 et r Fn . On a a = bq + r, o
q est le quotient de la division euclidienne de a par b. Bien entendu, q 1, do
a b + r Fn+1 + Fn = Fn+2 . La rciproque est claire.
Corollaire 2.26. Le cot en temps de lalgorithme dEuclide sur des entiers (a, b)
est en O(log min(a, b)).
Proposition 2.27. Le cot en nombre dtapes de lalgorithme dEuclide sur des
polynmes (A, B) est en O(min(deg A, deg B)).
Proposition 2.28. Le cot en oprations arithmtiques (additions, multiplications, divisions) de lalgorithme dEuclide sur des polynmes (A, B) (non constants)
est en O(deg A deg B).
Pour simplifier, on suppose que deg A > deg B.
Notons P0 = A, P1 = B, P2 , . . . , Pe , Pe+1 la suite de polynmes dfinie par le fait
que Pi+2 soit le reste de la division euclidienne de Pi par Pi+1 . On dfinit e par Pe 6= 0
et Pe+1 = 0. Notons di = deg Pi , de sorte que lon ait d0 > d1 > > de . Daprs le
calcul du cot dune division euclidienne, il existe une constante > 0 tel que le calcul
de Pi+2 connaissant Pi et Pi+1 ait un cot di+1 (di di+1 ) deg B (di di+1 ).
En faisant la somme, on obtient que le pgcd utilise un cot deg B (deg A
deg Pe ) deg A deg B.
Pour les coefficients de Bzout, il faut une analyse plus prcise. Notons Qi le quotient de la division euclidienne de Pi par Pi+1 (de sorte que Pi+2 = Pi Qi Pi+1 ).
Notons (Ui , Vi ) des polynmes dfinis par (U0 , V0 ) = (1, 0), (U1 , V1 ) = (0, 1), puis
(Ui+2 , Vi+2 ) = (Ui , Vi ) Qi (Ui+1 , Vi+1 ). Ils vrifient Pi = AUi + BVi .
On montre facilement que pour tout i, on a deg Ui+2 = deg Q1 + deg Q2 + +
deg Qi = d1 di+1 et deg Vi+2 = deg Q0 + + deg Qi = d0 di+1 . Ceci se vrifie
par rcurrence, en commenant par observer dune part que U2 = 1 et V2 = Q0 et
dautre part que U3 = Q1 et V3 = 1 + Q0 Q1 . Ensuite, dans la diffrence Ui+2 =
Ui Qi Ui+1 , le terme Qi Ui+1 est de degr strictement suprieur celui de Ui , de
sorte que deg Ui+2 = deg Ui+1 + deg Qi . Un raisonnement semblable vaut pour les Vi .
On sintresse ainsi au calcul de Ue et de Ve , vu que Pe = Ue A + Ve B. Les rsultats prcdents montrent que les polynmes U0 , U1 , . . . , Ue ont des degrs deg B
deg Pe1 < deg B. De mme, les polynmes V0 , V1 , . . . , Ve ont des degrs < deg A. Le
cot du calcul de Ui+2 en fonction de Ui , Ui+1 , Qi est donc en O((di di+1 )deg B). En

2.2. ALGORITHME DEUCLIDE

23

sommant ce cot pour les diffrents indice i, on obtient un cot en O(deg A deg B).
De mme, V2 se calcule certainement en O(deg A), puis pour i 1, le cot du calcul
de Vi+2 en fonction de Vi , Vi+1 , Qi est en O(deg A (di di+1 )), ce qui donne au total,
un cot aussi en O(deg A deg B).

CHAPITRE 3
CORPS FINIS

3.1. Premires observations

Proposition 3.1. Soit n un entier naturel. Lanneau Z/nZ est un corps si et
seulement si n est un nombre premier.
Ceci dcoule de la proposition 2.20 applique lanneau principal Z.
Dfinition 3.2. Soit p un nombre premier. On note Fp le corps Z/pZ.
Proposition 3.3. Soit F un corps fini. Il existe un unique nombre premier p tel
que p1F = 0, cest la caractristique de F. On peut considrer F comme un Fp -espace
vectoriel. Le cardinal q de F est pd o d = dimFp F.
Dfinition 3.4. Si on dispose dun corps fini q lments, il est permis de le
noter Fq .
Proposition 3.5. Soit Fq un corps fini q lments. Pour tout x Fq , on a
xq = x.
Le rsultat est vrai pour x = 0. Pour x 6= 0, il signifie que xq1 = 1, ce qui rsulte
du thorme de Lagrange appliqu au groupe multiplicatif F
q .
Proposition 3.6. Soit p un nombre premier. Soit A un anneau dans lequel p est
nul. Si (a, b) A2 , on a (a + b)p = ap + bp .


p
On utilise la formule du binme et on utilise le fait que p divise
pour
i
1 i p 1.
Dfinition 3.7. Soit p un nombre premier. Pour tout anneau A dans lequel p est
nul, on appelle Frobenius le morphisme danneaux : A A qui a associe ap .
Proposition 3.8. Soit F un corps fini q lments. Le groupe multiplicatif F
est cyclique.

26

CHAPITRE 3. CORPS FINIS

Si q = 2, le rsultat est trivial. Daprs le thorme de structure des groupes

abliens finis, il existe duniques entiers non nuls (a1 , . . . , ad ) avec ad |ad1 | . . . |a2 |a1
avec ad 2 tel que F soit isomorphe Z/a1 Z . . . Z/ad Z. Pour tout x F , on a
xa1 = 1, donc F a au plus a1 lments, do a1 . . . ad a1 , ce qui montre que d = 1,
et par consquent F ' Z/(q 1)Z.

3.2. Terminologie gnrale

3.2.1. Extensions, degrs.
Dfinition 3.9. Une extension de corps K/k est la donne de deux corps K et
k et dun morphisme (forcment injectif) : k K (parfois appel plongement ).
Bien souvent, on identifie k un sous-corps de K. Si K/k et L/k sont deux extensions,
un k-plongement de K dans L est un plongement K L qui vaille lidentit sur k.
Deux extensions K/k et L/k dun mme corps k sont dites isomorphes sil existe un
isomorphisme : K L induisant fixant les lments de k. Une extension K/k
est finie si K est un k-vectoriel de dimension finie.
Par exemple, pour tout corps fini F de caractristique p, on a une extension finie
F/Fp .
Dfinition 3.10. Soit K/k une extension finie. On note [K : k] la dimension de
K comme k-vectoriel, cest le degr de lextension K/k.
Proposition 3.11. Si K/k et L/K sont des extensions finies, alors lextension
compose L/k est une extension finie, et [L : k] = [L : K] [K : k].
Si a1 , . . . , an est une k-base de K et b1 , . . . , bm une K-base de L, alors les ai bj
forment une k-base de L.
Proposition 3.12. Soit k un corps. Soit A une k-algbre de dimension finie
comme k-espace vectoriel. Si A est intgre, alors A est un corps.
La multiplication par un lment non nul de A dfinit un endomorphisme k-linaire
injectif de A. Il est donc bijectif. En particulier, tout lment non nul de A est inversible.
3.2.2. Corps de rupture.
Proposition 3.13. Soit k un corps. Soit P k[X] un polynme non constant.
Lanneau k[X]/(P ) est un corps si et seulement si P est irrductible.
Ceci dcoule de la proposition 2.20 applique lanneau principal k[X].
Dfinition 3.14. Soit k un corps. Le corps de rupture dun polynme irrductible
P k[X] est une extension de k munie dun isomorphisme avec lextension k[X]/(P )
de k. Il sagit dune extension finie de degr deg P .

3.2. TERMINOLOGIE GNRALE

27

Proposition 3.15. Soit k un corps. Soit P k[X]. Soit K/k le corps de rupture
de P . Soit L/k une extension. Se donner un k-plongement K L revient se donner
un lment x de L tel que P (x) = 0.
On peut supposer que K = k[X]/(P ). On considre lapplication qui
un P
k-morphisme fP
: K L associe f ([X]). Pour tout tel f , on a videmment
n
n
i
f ([ i=0 ai X i ]) =
i=0 ai f (X) pour tous a0 , . . . , an lments de k. Lapplication
0
est injective : si f ([X]) = f ([X]), alors daprs la formule prcdente, f et f 0
concident sur tous les lments de k[X]. Lapplication est surjective. En
P effet,
soit x P
L tel que P (x) = 0. On considre lapplication g : k[X] L qui i ai X i
associe i ai xi . Il sagit videmment dun morphisme danneaux. On a videmment
g(P ) = 0. Par suite, g sannule sur lidal engendr par P ; par consquent, g induit
un morphisme danneaux g : k[X]/(P ) L envoyant bien X sur x.
Proposition 3.16. Soit K/k une extension finie de corps. Soit x K. Il existe
un unique polynme unitaire irrductible P k[X] tel que P (x) = 0 : cest le polynme
minimal de x. Le plus petit k-sous-corps de K contenant x, not k(x), est le corps de
rupture de P : k(x) ' k[X]/(P ). Le degr de x sur k est le degr de P , qui est aussi
[k(x) : x].
La famille 1, x, x2 , x3 , . . . nest pas une famille libre du k-vectoriel K. Le noyau
I du morphisme canonique de k-algbres k[X] K envoyant X sur x est non nul.
Notons P le polynme unitaire engendrant I. Le morphisme induit k[X]/(P ) K
est injectif, donc k[X]/(P ) est intgre : (P ) est un idal premier, cest--dire que P
est irrductible, etc.
Dfinition 3.17. Soit K/k une extension finie. Soit (x1 , . . . , xn ) un n-uplet dlments de K. On note k[x1 , . . . , xn ] (ou k(x1 , . . . , xn )) le plus petit k-sous-corps de K
contenant les xi : il est form des valeurs des polynmes de k[X1 , . . . , Xn ] valus en
les xi .
Dfinition 3.18. Soit K/k une extension finie. On dit que K/k admet un lment
primitif x sil existe x K tel que K = k[x].
Remarque 3.19. Toute extension K/k de corps finis admet un lment primitif :
prendre un gnrateur du groupe K .
Remarque 3.20. Si P k[X] est un polynme irrductible de degr d, on peut
reprsenter les lments du corps de rupture k[X]/(P ) (on note x la classe de X),
sous la forme a0 + a1 x + + ad1 xd1 avec (a0 , . . . , ad1 ) k d , autrement dit sous
la forme Q(x) o Q k[X] est un polynme de degr au plus d 1. Pour exprimer un
produit Q1 (x)Q2 (x) sous cette forme, on considre le reste R de la division euclidienne
de Q1 Q2 par P , et on a Q1 (x)Q2 (x) = R(x) dans le corps de rupture k[X]/(P ).
Proposition 3.21. Soit P k[X] un polynme de degr d 2. Alors, P est
irrductible si et seulement si P na de racine dans aucune extension de k de degr
e b d2 c.

28

CHAPITRE 3. CORPS FINIS

Si P est rductible, il scrit P = P1 . . . Pk avec Pi des polynmes irrductibles. On

peut supposer que P1 est celui qui a le plus petit degr e. Comme k 2, on a bien
sr deg P1 = e d2 . Notons K le corps de rupture de P1 sur P . K est une extension
de degr e dans laquelle P1 , et donc P , admettent une racine.
Inversement, si K est une extension de degr e d2 de k dans laquelle P admettrait
une racine x. Notons Q le polynme minimal de x, cest un polynme irrductible.
Comme P (x) = 0, Q est bien un diviseur de P . Le degr de Q est celui de lextension
k[x]/k qui est infrieur celui de K/k qui est lui-mme infrieur d2 .
Remarque 3.22. Ce critre est trs utile pour les corps finis puisque nous verrons
que ceux-ci nadmettent isomorphisme prs quune seule extension de degr donn.
3.2.3. Composes de deux extensions.
Proposition 3.23. Soit K/k et L/k deux extensions finies. Alors, il existe une
extension M/k P
munie de deux k-plongements M/K et M/L, et telle que tout lment
de M scrive i xi yi avec les xi dans K et les yi dans L (on note M = KL). On
dit que M/k est une extension compose de K/k et de L/k.
On commence par le cas o K/k admet un lment primitif x. Soit P le polynme
minimal de x. On a K = k[X]/(P ). On choisit un facteur irrductible Q de P vu
comme lment de L[X]. On note M = L[X]/(Q). Par construction, M est une kextension de L. Par ailleurs, M contient une racine privilgie de Q, donc de P , on
peut aussi en faire une extension de K en voyant X sur X. Par consquent, on a bien
M = KL.
Dans le cas gnral, on procde par rcurrence sur [K : k]. Si [K : k] = 1, cest
trivial, sinon, on choisit x K k, on note K 0 = k[x]. On applique ce qui prcde pour
construire une extension compose M 0 /k de K 0 /k et de L/k. On considre ensuite
les extensions K et M 0 de K 0 , le degr [K : K 0 ] est strictement moindre que [K : k],
lhypothse de rcurrence permet de trouver une extension compose M/K 0 de K/K 0
et de M 0 /K 0 .
3.2.4. Polynmes scinds, corps de dcomposition.
Dfinition 3.24. Un polynme non nul P k[X] est dit scind sil peut scrire
(X a1 ) . . . (X an ) avec a1 , . . . , an et des lments de k. On dit aussi que P a
toutes ses racines dans k.
Un diviseur dun polynme scind est encore scind. Le produit de deux polynmes
scinds est scind.
Proposition 3.25. Soit P k[X] un polynme non nul. Il existe une extension
finie K/k telle que, en tant qulment de K[X], P soit scind.
On peut supposer que P est unitaire. On procde par rcurrence sur deg P . Si
deg P 1, K = k convient. Si P nest pas irrductible, on crit P = QR avec Q et
R non constants (unitaires), et donc de degrs strictement plus petits que celui de P .
On choisit L une extension finie de k dans laquelle Q est scind. On considre ensuite
R comme lment de L[X], et on choisit une extension finie K/L telle que R soit

29

3.2. TERMINOLOGIE GNRALE

scind sur K. Les deux polynmes Q et R sont scinds sur K, leur produit P lest
donc aussi.
Ainsi, on peut supposer que P est irrductible. On peut considrer un corps de
rupture L de P . Il existe a L tel que P (a) = 0. On peut factoriser P L[X] sous
la forme P = (X a)Q, avec Q L[X]. Par hypothse de rcurrence, on peut choisir
une extension K de L scindant le polynme Q. Le polynme P est scind sur K.
Dfinition 3.26. Soit k un corps. Soit P k[X], P non constant. Un corps de
dcomposition de P est une extension K/k telle que P soit scind sur K, et que si on
note x1 , . . . , xn les racines de P dans K, alors K = k(x1 , . . . , xn ).
Proposition 3.27. Soit k un corps. Soit P k[X], P non constant. Si K/k et
L/k sont deux corps de dcomposition de P , alors K et L sont isomorphes.
On peut supposer que K et L sont contenus dans une mme extension finie M
de k. Les racines de P dans M sont la fois dans K et dans L. Or, K et L sont
prcisment les sous-k-algbres engendres par ces racines, donc K = L.
3.2.5. Polynmes sparables.
Dfinition 3.28. Soit P k[X]. Si P =

ai X i , on pose P 0 =

i6=0

iai X i1 .

Proposition 3.29. Soit k un corps. Soit P = (X a1 ) . . . (X an ) avec ai k.

Les conditions suivantes sont quivalentes :
(i) P P 0 = 1 ;
(i bis) les polynmes P et P 0 nont pas de racine commune ;
(ii) les lments ai sont distincts.
Comme P est scind, on Q
a bien entendu (i)(i bis).
Observons que P 0 (ai ) = j6=i (ai aj ). Par consquent, si les lments a1 , . . . , an
ne sont pas distincts, il existe i tel que P 0 (ai ) = 0. Ceci montre la contrapose de
(i bis)(ii).
Inversement, si P et P 0 ont une racine commune, il existe i tel que P 0 (ai ) = 0,
ce qui montre quil existe j 6= i tel que ai = aj , ceci montrant la contrapose de
(ii)(i bis).
Lemme 3.30. Soit k un corps. Soit (P, Q) k[X]2 . Soit K/k une extension.
Calculer le pgcd de P et Q en tant qulments de k[X] ou de K[X] donne le mme
rsultat.
Appliquer lalgorithme dEuclide dans k[X] ou dans K[X] donne videmment le
mme rsultat.
Dfinition 3.31. Soit k un corps. Soit P k[X] un polynme non nul. On dit
que P est sparable si P P 0 = 1, autrement dit, daprs ce qui prcde, que dans
un corps de dcomposition de P , P na pas de racine multiple, ou encore que dans un
corps de dcomposition de P , P na pas de racine commune avec P 0 .
Proposition 3.32. Soit k un corps. Soit P k[X] un polynme irrductible.
Alors P 0 est sparable si et seulement si P 0 6= 0.

30

CHAPITRE 3. CORPS FINIS

P est sparable si et seulement si P et P 0 sont premiers entre eux, cest--dire, P

tant irrductible, que P divise P 0 . Pour des raisons de degr, cela revient dire que
P 0 est nul.

3.3. Existence et unicit des corps finis

Proposition 3.33. Soit p un nombre premier. Soit n 1. On pose q = pn . On
note K/Fp un corps de dcomposition de X q X Fp [X]. Alors, K est un corps fini
q lments.
Le polynme X q X Fp [X] est videmment sparable, donc K contient exactement q racines du polynme X q X. On considre le morphisme danneaux : K K
dfini par = n . On a (a) = aq pour tout a K. Lensemble des lments de K
tels que a = (a) est donc un sous-anneau B de K. Comme K est engendr comme
Fp -algbre par les lments de B, on a K = B : tous les lments de K sont des
racines de X q X.
Proposition 3.34. Soit p un nombre premier. On se donne deux entiers naturels
non nuls m et n. Soit F un corps fini pm lments. Soit F0 un corps fini pn
lments. Il existe un plongement F F0 si et seulement si m divise n. En particulier,
deux corps finis de mme cardinal sont isomorphes.
Sil existe un plongement F F0 , on peut appliquer la formule de multiplicativit
des degrs : [F0 : Fp ] = [F0 : F] [F : Fp ].
n
. On peut supposer que F et
On suppose que m divise n. Posons q = pm et d = m
0
00
F sont contenus dans un mme corps fini F . Les lments de F (resp. F0 ) sont les
d
racines de X q X (resp. X q X) dans F00 . Par consquent, il suffit de montrer que
d
si x F00 est tel que xq = x, alors xq = x, ce qui sobtient aussitt par rcurrence
sur d.

3.4. Polynmes irrductibles sur un corps fini

Dfinition 3.35. Soit Fq un corps fini q lments. Pour toute extension finie
K/Fq on note q : K K le morphisme de Frobenius relatif Fq , il est dfini par la
formule q (a) = aq . Il sagit dun Fq -automorphisme de K.
Proposition 3.36. Soit Fq un corps fini q lments. Soit P Fq [X] un polynme irrductible unitaire de degr d. Soit E/Fq le corps de rupture de P , avec x E
tel que P (x) = 0. Le plus petit entier k 1 tel que k
q (x) = x est d, on a la relation :
P =

d1
Y

(X i
q (x))

i=0

Le corps E est un corps de dcomposition de P . En outre, P est sparable.

3.4. POLYNMES IRRDUCTIBLES SUR UN CORPS FINI

31

Le corps E a q d lments, donc xq = x, cest--dire d

q (x) = x. Le groupe
Z agit sur E de faon ce que nFy = n
(y).
Lorbite
de x est videmment
q
x, q (x), . . . , k1
(x)
o
k
est
le
plus
petit
entier
non
nul
tel
que
k
q
q (x) = x. Comme
P (q (y)) = q (P (y)), si y E est une racine de P , alors q (y) aussi. Ainsi, les lments i
q (x)) de E pour tout 0 i k 1 sont des racines distinctes de P . Si on
Qd1
pose Q = i=0 (X i
q (x)) E[X], on obtient que Q divise P . Les coefficients de
Q sont manifestement fixs par q , donc Q Fq [X]. Ce polynme unitaire Q est
un diviseur non trivial du polynme irrductible unitaire P , on a donc Q = P (et
k = d). On vient de voir que P est scind sur E, et E est engendr par la racine x ;
par consquent, E est un corps de dcomposition de P . Le fait que P soit sparable
est vident daprs sa factorisation dans E[X].
Proposition 3.37. Soit Fq un corps fini q lments. Soit E une extension finie
de Fq de degr d. Alors, Aut(E/Fq ) est un groupe cyclique dordre d engendr par
q .
Daprs la construction des corps finis, on sait dj que le sous-groupe cyclique
de Aut(E/Fq ) engendr par q est dordre d. Il sagit de montrer que tous les Fq automorphismes de E sont dans ce sous-groupe. On peut choisir un lment primitif x
de E/Fq . Notons P le polynme minimal de x sur Fq . Lensemble des Fq -morphismes
E E sidentifie lensemble des solutions de P dans E. Daprs la proposition 3.36,
toutes ces solutions sont de la forme i
q (x) pour 0 i d 1, ce qui permet de
conclure.
Proposition 3.38. Soit Fq un corps q lments. Soit n 1 un entier. Alors,
n
dans Fq [X], X q X sidentifie au produit des polynmes irrductibles unitaires de
Fq [X] dont les degrs divisent n.
On considre une extension E/Fq de degr n et laction de Z/nZ sur E dfinie de
sorte que 1 agisse par q . Deux lments de E sont dans la mme orbite si et seulement
sils ont mme polynme minimal. Le polynme minimal dun lment x E est le
degr du corps [Fq (x) : Fq ], qui divise donc n = [E : Fq ]. Inversement, tout polynme
unitaire irrductible P de degr d divisant n admet un corps de rupture Fq [X]/(P ) qui
peut sidentifier un sous-Fq -corps de E (cf. dmonstration de la proposition 3.34),
donc P est le polynme minimal dun lment de E.
Bref, on peut identifier lensemble des orbites de E sous q lensemble des polynmes irrductibles unitaires
outre, pour une telle orbite O
Q de degr divisant n. En
n
associe P , on a P = xO (X x). Comme X q X sidentifie au produit des
(X x) pour x E, on en dduit aussitt le rsultat.
Corollaire 3.39. Soit Fq un corps q lments. Pour tout entier d 1, on note
Nd le nombre de polynmes unitaires irrductibles de degr d dans Fq . Alors, pour
tout n 1, on a la relation :
X
qn =
dNd .
d|n

32

CHAPITRE 3. CORPS FINIS

Remarque 3.40. Pour tout d 1, Nd 1. En particulier, il existe un polynme

irrductible unitaire P de degr d sur Fp . Si on sait dterminer un tel P , on peut
construire le corps fini Fpd en prenant le corps de rupture de P sur Fp . Si on note
x la racine privilgie de P dans ce corps de rupture, tout lment de Fpd peut tre
reprsent sous la forme a0 + a1 x + + ad1 xd1 o (a0 , . . . , ad1 ) est un d-uplet
dentiers modulo p. Ceci permet donner une reprsentation informatique des lments
dans un corps fini.
Qk
Dfinition 3.41. Soit n N {0}. On peut crire n = i=1 pei i o les pi sont
des nombres premiers distincts de ei 1. Sil existe i tel que ei 2, on pose (n) = 0,
sinon, (n) = (1)k (en particulier, (1) = 1). est la fonction de Mbius.
Proposition 3.42. Avec les notations du corollaire 3.39, on a :
X
n
(d)q d .
nNn =
d|n

Voici une dmonstration possible (ce nest pas la plus savante). On a vu dans la
dmonstration de la proposition 3.38 que nNn tait gal au nombre dlments de Fqn
qui sont exactement de degr n sur Fq , cest--dire ne sont dans aucun sous-corps Fqd
de Fqn pour d divisant n et d 6= n. On peut donc crire
[
nNn = q n #(
Fq d )
d|n,d6=n

Qk

crivons n = i=1 pei i avec les pi premiers distincts et ei 1. Dans la runion cidessus, il suffit de considrer les d de la forme pni . Notons Ai = F pni . On a la formule
q

k
[
i=1

Ai =

k
X
l=1

(1)l1

#(Ai1 Ail ) .

i1 <<il

Lemme 3.43. Si d et e deux diviseurs de n, alors lintersection de Fqd et de Fqe

dans Fqn est Fqm o m est le pgcd de d et e.
On sait que Fqm est contenu dans Fqd et dans Fqm , il est donc contenu dans leur
intersection. Inversement, le degr sur Fq de lintersection des deux corps doit diviser
d et e, donc diviser m. Linclusion prcdente est donc une galit.
En appliquant ce lemme, on obtient, avec les notations ci-dessus :
n

#(Ai1 Ail ) = q pi1 ...pil .

Lensemble dindices l, i1 < < il peut tre identifi lensemble des diviseurs d
de p1 . . . pk autres que 1 par les correspondances d = pi1 . . . pil et l = (d). On obtient
ainsi :
X
n
nNn = q n +
(d)q d
16=d|p1 ...pk

3.4. POLYNMES IRRDUCTIBLES SUR UN CORPS FINI

Ceci se rcrit aussitt

nNn =

33

(d)q d

d|p1 ...pk

Si d est un diviseur de n ne divisant pas p1 . . . pk , on a (d) = 0, ce qui donne la

formule voulue.

CHAPITRE 4
FACTORISATION DANS Fq [X]

Lobjet de ce chapitre est dexpliquer comment on peut procder pour factoriser

un polynme P Fq [X] sous la forme dun produit de polynmes irrductibles.
Une question voisine consiste, tant donn un polynme non constant, pouvoir
affirmer soit que P est irrductible, soit que P ne lest pas et dexhiber un facteur
non trivial. Il suffit de rpondre cette question pour rpondre la premire : si on
peut exhiber des facteurs non triviaux, on peut applique rcursivement lalgorithme
de factorisation des polynmes non constants Q et R tels que P = QR qui auront
t dtermins.
4.1. Rduction au cas des polynmes sans facteur carr
4.1.1. Polynmes sans facteurs carrs, polynmes sparables.
Dfinition 4.1. Soit k un corps. Soit P k[X], P 6= 0. On dit que P est sans
facteur carr sil nexiste pas Q k[X] non constant tel que Q2 divise P . Autrement
dit, aucun polynme irrductible napparat avec multiplicit au moins 2 dans la
dcomposition de P .
Dfinition 4.2. Soit k un corps. On dit que k est parfait si pour tout polynme
irrductible P k[X], alors P est sparable (cest--dire que P 0 6= 0).
Proposition 4.3. Soit k un corps parfait. Soit P k[X], P 6= 0. Alors, P est
sparable si et seulement si P est sans facteurs carrs.
Si P admet un facteur carr, il existe Q non constant et R tels que P = Q2 R, do
P = Q(2Q0 R + QR0 ), ainsi Q divise le pgcd de P et de P 0 , P nest pas sparable.
Inversement, supposons que P nait pas de facteur carr. On peut crire P =
Qk
i=1 Pi o les Pi sont des polynmes irrductibles trangers deux--deux. Montrons
que Pi ne divise pas P 0 (de sorte que P et P 0 seront premiers entre
Q eux, cest--dire
que P sera sparable). Il vient aussitt que P 0 est congru Pi0 j6=i Pj modulo Pi .
Q
Pour conclure, il suffit de montrer que Pi ne divise pas Pi0 j6=i Pj , ce qui est assur
par le fait que Pi0 soit premier Pi .
0

36

CHAPITRE 4. FACTORISATION DANS Fq [X]

Thorme 4.4. Soit k un corps. Alors, k est un corps parfait si et seulement si k

est de caractristique 0 ou bien que k est de caractristique p > 0 et que le morphisme
de Frobenius x 7 xp dfinit un automorphisme de k.
Il est vident que dans un corps de caractristique zro, le polynme driv dun
polynme irrductible est non nul. Supposons que k soit de caractristique p > 0.
Supposons que le morphisme de Frobenius soit surjectif, montrons que k est parfait.
Soit P k[X] un polynme tel que P 0 = 0. La condition P 0 = 0 signifie que P est en
fait un polynme en X p . Les coefficients de P admettent
dans k,
P des racines p-imesP
on peut donc trouver des lments ai k tels que P = i api X p . Posons Q = i ai X.
On a P = Qp , donc P nest pas irrductible. Ainsi, tout polynme irrductible dans
k[X] est sparable. Inversement, supposons quon ait a k tel que X p a nait pas de
racine dans k et montrons que k nest pas parfait. Considrons une extension finie L
de k scindant X p a. Notons b une racine p-ime de a dans L. Comme le morphisme
de Frobenius est un morphisme de corps (donc injectif), llment b est lunique racine
de X p a dans L, do X p a = (X b)p . Montrons que P = X p a k[X] est
irrductible. Si Q L[X] est un polynme unitaire divisant P (et qui nest ni 1 ni
P ), alors, en raisonnant dans L[X], on obtient quil existe 1 i p 1 tel que
Q = (X b)i . Ce polynme Q nappartient pas k[X]. En effet, le coefficient de X i1
dans Q est ib (oppos de la somme des racines), qui nappartient pas k. Ainsi, P
est irrductible, mais P 0 = 0, ce qui montre que k nest pas parfait.
Corollaire 4.5. Tout corps fini k est parfait, et un polynme P k[X] est sparable si et seulement sil est sans facteur carr.
4.1.2. Algorithme.
Proposition 4.6. Soit k un corps parfait. Pour factoriser des polynmes P dans
k[X], on peut supposer que P est sans facteur carr.
Lemme 4.7. Soit k un corps parfait. Soit P k[X] tel que P 0 = 0. Alors, il
existe un polynme Q k[X] tel que P = Qp .
P
On peut crire P = i ai X ip puisque les coefficients de X j pour p ne divisant pas
p sont nuls. Comme
k est parfait, on peut extraire une racine p-ime bi de ai dans k
P
et poser Q = i bi X i . On a bien P = Qp .
Remarque 4.8. Si k = Fp , pour tout a k, on a ap = a, il est donc trivial
d1
dextraire la racine p-ime dun lment. Si k = Fq avec q = pd , alors ap
est une
racine p-ime de a.
Supposons quon dispose dun algorithme de factorisation dans le cas de polynmes
sans facteur carr et donnons un algorithme permettant de dterminer une factorisation dans le cas gnral :
Algorithme pour se ramener aux polynmes sans facteur carr 4.9
Soit k un corps parfait. Soit P k[X], P non constant. On calcule P 0 . Si P 0 = 0,
le lemme 4.7 et la remarque subsquente fournissent un polynme Q k[X] tel que
P = Qp , on peut renvoyer factoriser Q rcursivement pour obtenir la factorisation de

4.2. ALGORITHME DE BERLEKAMP

37

P . Sinon, on calcule Q = P P 0 . Si Q est constant (et non nul puisque P 0 6= 0), P est
sans facteur carr, on peut lui appliquer lalgorithme de factorisation des polynmes
sans facteur carr. Sinon, Q est un diviseur non trivial de P , on peut factoriser
(rcursivement) Q et P/Q pour obtenir une factorisation de P .
4.2. Algorithme de Berlekamp
On fixe une fois pour toutes un corps fini Fq et un polynme unitaire sparable
P Fq [X] de degr d 1. Daprs la proposition 4.3, il existe un entier e 1
et des polynmes unitaires irrductibles P1 , . . . , Pe Fq [X] distincts tels que P =
P1 P2 . . . Pe .
4.2.1. Dtermination du nombre de facteurs irrductibles.
Dfinition 4.10. On note A la Fq -algbre A = Fq [X]/(P ).
Daprs le thorme chinois, on a :
Proposition 4.11. On a un isomorphisme canonique de Fq -algbres :
A = Fq [X]/(P ) ' K1 K2 Ke ,
o pour tout i, Ki est le corps de rupture de Pi sur Fq .
Dfinition 4.12. On note q : A A lapplication a 7 aq . Il sagit dun endomorphisme Fq -linaire de lanneau A. On note A0 le sous-anneau de A form des
lments a A tels que q (a) = a.
Proposition 4.13. Le sous-anneau A0 de A est un Fq -espace vectoriel de dimension e.
On dispose dun isomorphisme A ' K1 Ke de Fq -algbres. Soit a =
(a1 , . . . , ae ) un lment de K1 Ke . On a aq = (aq1 , . . . , aqe ). Dire que aq = a revient demander que les lments ai appartienne au sous-corps Fq du corps Ki pour
tout i. Lensemble A0 sidentifie donc Feq ; sa dimension comme Fq -espace vectoriel
est e.
Dfinition 4.14. On note x la classe de X dans le quotient A = Fq [X]/(P ).
La famille (1, x, x2 , . . . , xd1 ) est une base du Fq -espace vectoriel A, on note q la
matrice du Fq -endomorphisme q : A A dans la base (1, x, x2 , . . . , xd1 ).
La proposition retenir constitue le principe de lalgorithme de factorisation de
Berlekamp :
Algorithme de Berlekamp pour dterminer le nombre de facteurs irrductibles 4.15
Soit P un polynme sparable de degr d 1 sur Fq . On considre la matrice q
coefficients dans Fq dont la i-me colonne (pour 0 i d 1) est constitue des
coefficients du polynme X iq mod P . Le nombre de facteurs irrductibles e de P est
la dimension du noyau de la matrice q Id (noyau dont on peut dterminer une
base grce lalgorithme du pivot de Gau).

38

CHAPITRE 4. FACTORISATION DANS Fq [X]

Le noyau de q Id sidentifie lensemble des a A tels que aq = a, cest--dire

aux lments de A0 qui est bien un Fq -espace vectoriel de dimension e daprs ce qui
prcde.
Remarque 4.16. Il existe diverses mthodes plus ou moins sophistiques pour
dterminer la matrice q . Une faon de faire consiste dterminer W = X q mod P ,
puis dterminer les coefficients de la matrice q colonne par colonne : si W i mod P
a t determin, en multipliant le rsultat par W et en prenant le reste de la division
euclidienne modulo P , on obtient W i+1 mod P .
4.2.2. Dtermination dun facteur non trivial. Si e = 1, le polynme P
Fq [X] est irrductible. Si e 2, il reste expliciter un facteur non trivial de P :
Proposition 4.17. Soit P un polynme sparable de degr d 1 sur Fq . Soit
Q Fq [X] (non constant, et de degr < d) un vecteur propre de q pour la valeur
propre 1. Alors, il existe Fq tel que le pgcd de Q + et de P soit un facteur non
trivial de P .
Ainsi, en calculant le pgcd de Q+ et de P pour parcourant Fq avec lalgorithme
dEuclide, on obtient un facteur non trivial de P .

Montrons la proposition. On utilise lisomorphisme canonique f : A K1 Ke .

Posons (a1 , . . . , ae ) = f (Q). Lhypothse selon laquelle q (Q) = Q signifie que pour
tout i, ai appartient au sous-corps Fq de Ki . Dire que Q nest pas constant signifie que
les ai ne sont pas tous gaux entre eux. Posons = a1 . Par construction, f (Q+) est
non nul mais au moins une (et loccurrence la premire) de ses coordonnes sannule.
Ainsi, P1 divise Q + ; le pgcd de P et de Q + est un facteur non trivial de P .

CHAPITRE 5
RSULTANTS

5.1. Dfinitions
Dfinition 5.1. Soit A un anneau. Soit n N. On note A[X]n ou A[X]<n+1
le sous-A-module de A[X] form des polynmes de degr < n. La base canonique de
A[X]n est 1, X, X 2 , . . . , X n . La base anticanonique est X n , . . . , X, 1.
Dfinition 5.2. Soit A un anneau. Soit (m, n) N2 . Soit P A[X]m . Soit
Q A[X]n . On note Resm,n (P, Q) A le dterminant du morphisme qui (U, V )
A[X]<n A[X]<m associe U P + V Q A[X]<m+n dans les bases anticanoniques ,
savoir (X n1 , 0), . . . , (X, 0), (1, 0), (0, X m1 ), . . . , (0, X), (0, 1) pour le A-module de
dpart et (X m+n1 , X m+n2 , . . . , X, 1) pour le A-module darrive.
Proposition 5.3. Soit P = vm X m + +v1 X +v0 A[X]m . Soit Q = wn X n +
+ w1 X + w0 A[X]n . Alors, Resm,n (P, Q) est le dterminant de la matrice de
Sylvester Sylm,n (P, Q) (carre de taille m + n) :

vm vm1
...
v0
0
0
...
0
0
vm
vm1 . . . v0
0
...
0

.
.
.
.
.
.
.
.
0
.
.
.
.
0
0
0

..
..
..
..

0
.
.
.
.
0
.
.
.
0

0
.
.
.
.
.
.
0
v
v
.
.
.
v
m
m1
0

wn
.
.
.
.
.
.
.
.
.
w
w
0
.
.
.
1
0

.
.
.
.
.
.
0
.
.
.
wn
w1
w0
0
0
0
wn
... ...
...
w1 w0
La matrice de Sylvester est la transpose de la matrice du morphisme dfini plus
haut dans les bases considres.
Proposition 5.4. Soit A un anneau (intgre). Soit m 1. Soit P A[X]m .
On suppose que le coefficient vm de X m dans P est non nul. On note Disc P =

40

m(m1)
1
2
vm (1)

CHAPITRE 5. RSULTANTS

Resm,m1 (P, P 0 ). Il sagit dun lment de A, appel discriminant de

P.

Sur la premire colonne de la matrice de Sylvester Sylm,m1 (P, P 0 ), tous les coefficients, sauf peut-tre deux, sont nuls. Les deux autres sont les coefficients de X m
dans P et de X m1 dans P 0 , savoir vm et mvm . On peut dfinir une matrice
Syl0m,m1 (P, P 0 ) en remplaant respectivement les coefficients vm et mvm de la premire colonne de Sylm,m1 (P, P 0 ) par 1 et m. Le discriminant de P est le dterminant
de cette matrice Syl0m,m1 (P, P 0 ) (ceci a un sens mme si lanneau A nest pas intgre).
Par construction, ce dterminant est un lment de A satisfaisant :
vm Disc P = (1)

m(m1)
2

Resm,m1 (P, P 0 ) .

5.2. Formules
Sauf mention du contraire, dans les noncs suivants, P et Q sont des polynmes
coefficients dans un anneau A respectivement de degrs au plus m et n.
Proposition 5.5. Soit : A B un morphisme danneaux. On note P (resp.
Q ) le polynme de B[X] obtenu en appliquant aux coefficients de P (resp. Q).
Alors, Resm,n (P , Q ) = (Resm,n (P, Q)).
Proposition 5.6. En particulier, pour le morphisme danneaux Z Z/pZ
o p est un nombre premier, si P et Q sont coefficients entiers et que P et Q
sont les rductions modulo p de ces polynmes P et Q, alors la classe modulo p de
Resm,n (P, Q) est Resm,n (P , Q). En particulier, Resm,n (P , Q) = 0 si et seulement si
p divise Resm,n (P, Q).
Proposition 5.7. Soit (, ) A2 . Resm,n (P, Q) = n m Resm,n (P, Q).
Res0,n (, Q) = n . Resm,0 (P, ) = m .
Proposition 5.8. Resn,m (Q, P ) = (1)mn Resm,n (P, Q).
Calculer Resn,m (Q, P ) revient calculer le dterminant intervenant dans le calcul
de Resm,n (P, Q) en changeant la base du A-module de dpart en inversant les vecteurs
de base associs aux variables U et V , le nombre dinversions de cette permutation
est mn.
Proposition 5.9. Soit A. Resm,n (P (X + ), Q(X + )) = Resm,n (P, Q).
On peut calculer Resm,n (P (X + ), Q(X + )) est utilisant des bases autres
que celles considres dans la dfinition 5.2. La matrice du morphisme (U, V ) 7
U P (X + )V (X + ) dans les bases (((X + )n1 , 0), . . . , (X + , 0), (1, 0), (0, (X +
)m1 ), . . . , (0, X + ), (0, 1)) et ((X + )m+n1 , . . . , X + , 1) de A[X]<n A[X]<m
et A[X]<m+n est gale la matrice du morphisme (U, V ) 7 U P + V Q dans les
bases de la dfinition 5.2 ; le rsultat est donc Resm,n (P, Q). Or, manifestement,
les matrices de changement de base entre les bases considres ici et celles de la
dfinition 5.2 sont triangulaires et leurs diagonales ne contiennent que des 1. On en
dduit lgalit voulue.

5.2. FORMULES

41

Proposition 5.10. Soit A. Resm+1,n ((X + )P, Q) = Resm,n (P, Q)

Res1,n (X , Q). En outre, Res1,n (X , Q) = Q().
Daprs la proposition 5.9, on peut supposer que = 0. Sur la dernire colonne de la
matrice de Sylvester Sylm+1,n (XP, Q), tous les coefficients sont nuls sauf peut-tre le
dernier qui vaut Q(0). En dveloppant le dterminant de Sylm+1,n (XP, Q) par rapport
cette colonne, on obtient aussitt lgalit Resm+1,n (XP, Q) = Resm,n (P, Q) Q(0).
Lgalit Res1,n (X, Q) = Q(0) est vidente.
Proposition 5.11. Soit (a1 , . . . , am )Q Am . On suppose que P = (X
m
a1 ) . . . (X am ). Alors, Resm,n (P, Q) = i=1 Q(ai ).
Cette formule se dduit aussitt de la proposition 5.10 par rcurrence sur m.
Proposition 5.12. Soit (a1 , . . . , am ) Am . Soit (b1 , . . . , bn ) An . On suppose
que
Q P = (X a1 ) . . . (X am ). et que Q = (X b1 ) . . . (X bn ). Alors, Resm,n (P, Q) =
1im,1jn (ai bj ).
Cela rsulte aussitt de la proposition 5.11.
m
Proposition 5.13.
Q Soit (a21 , . . . , am ) A . On pose P = (X a1 ) . . . (X am ).
Alors, Disc P = i<j (ai aj ) .

Q
En utilisant la formule de la proposition 5.11 et lgalit P 0 (ai ) = j6=i (ai aj )
Q
pour tout i, on obtient que Resm,m1 (P, P 0 ) = i6=j (ai aj ), ce qui permet de
conclure.
Proposition 5.14. On note wn le coefficient de X n dans Q. Alors Resm+1,n (P, Q) =
(1)n wn Resm,n (P, Q)
On note vm le coefficient de X m dans P . Alors Resm,n+1 (P, Q) = vm Resm,n (P, Q)
Proposition 5.15. On suppose m n. Soit S A[X]mn . Alors, Resm,n (P +
SQ, Q) = Resm,n (P, Q).
Notons , : A[X]<n A[X]<m A[X]<m+n les applications A-linaires dfinies par (U, V ) = U P + V Q et (U, V ) = U (P + SQ) + V Q. On peut considrer
lendomorphisme de A[X]<n A[X]<m dfini par (U, V ) = (U, V + U S). On a
videmment = . Comme les rsultants tudis ici sont les dterminants de et
dans les bases considres dans la dfinition 5.2, il suffit de montrer que lendomorphisme est de dterminant 1, ce qui rsulte du fait que dans la base anticanonique
de A[X]<n A[X]<m , sa matrice est triangulaire suprieure.
Proposition 5.16. On suppose que A est un corps. Supposons m = deg P n =
deg Q > 0. Notons R le reste de la division euclidienne de P par Q. Si R = 0, alors
Resm,n (P, Q) = 0, sinon Resm,n (P, Q) = Resm,n (R, Q) = (1)mn wnmr Resn,r (Q, R)
o wn est le coefficient dominant de Q et r = deg R.

42

CHAPITRE 5. RSULTANTS

Pour tout 0 r m tels que R k[X]r , on a :

Resm,n (P, Q)

Resm,n (R, Q)

(1)(mr)n wnmr Resr,n (R, Q)

(1)mn wnmr Resn,r (Q, R)

Si R 6= 0, on applique la formule obtenue dans le cas r = deg R pour conclure ; sinon,

on lapplique par exemple avec r = 0, et on conclut en utilisant que Resn,0 (Q, 0) = 0.
Remarque 5.17. Cette proposition fournit un algorithme pour dterminer le rsultant de deux polynmes. Sa complexit est manifestement du mme ordre que celle
de lalgorithme dEuclide.
5.3. Proprits
Proposition 5.18. Soit A un anneau. Soit P A[X]m . Soit Q A[X]n . Il
existe U A[X]<n et V A[X]<m tels que U P + V Q = Resm,n (P, Q).
Notons M la transpose de la comatrice de la transpose de la matrice de Sylvester
Sylm,n (P, Q). On a
Resm,n (P, Q) Im+n = t Sylm,n (P, Q) M .
Si on note W la premire colonne de la matrice M , on obtient :

..

t
.

= Sylm,n (P, Q) W .

0
Resm,n (P, Q)
La traduction en termes dapplications linaires de lexistence dun vecteur-colonne
W satisfaisant cette relation est quil existe (U, V ) vrifiant les conditions de degr
ci-dessus tels que U P + V Q = Resm,n (P, Q).
Proposition 5.19. Soit k un corps. Soit P k[X]m . Soit Q k[X]n . On
suppose m = deg P , n = deg Q et (m, n) 6= (0, 0). Les conditions suivantes sont
quivalentes :
(i) Resm,n (P, Q) 6= 0 ;
(ii) Pour tout R k[X]<m+n , il existe U k[X]<n et V k[X]<m tels que
UP + V Q = R ;
(iii) Il existe U k[X]<n et V k[X]<m tels que U P + V Q = 1 ;
(iv) P et Q sont premiers entre eux.
Si E/k est une extension de k sur laquelle P ou Q est scind, on peut rajouter la
condition suivante :
(v) P et Q nont pas de racines communes dans E.
La non-annulation du dterminant Resm,n (P, Q) de la matrice de Sylvester quivaut la surjectivit de lapplication linaire associe, cest--dire que (i) (ii). Ensuite, on a bien sr, (ii) = (iii) = (iv). Montrons (iv) = (ii). Pour R k[X]<m+n ,

5.4. EXEMPLES

43

il existe videmment U et V dans k[X] tels que U P + V Q = R ; il reste montrer que

lon peut sarranger pour que U et V vrifient les conditions de degr nonces dans
(ii). Soit U 0 = U AQ k[X]<n le reste de la division euclidienne de U par Q. On
pose V 0 = V + AP . On vrifie aussitt que U 0 P + V 0 Q = R. Comme V 0 Q = R U 0 P
et que R et U 0 P sont de degrs < m + n, il vient que V 0 k[X]<m . Pour lquivalence
(i) (v), on peut supposer que cest P est scind sur E, et le rsultat dcoule de
la formule de la proposition 5.11.
Proposition 5.20. Soit k un corps. Soit P k[X]m . Soit Q k[X]n . Les
conditions suivantes sont quivalentes :
Resm,n (P, Q) = 0 ;
deg P < m et deg Q < n, ou P et Q ne sont pas premiers entre eux (cest--dire
admettent une racine dans une extension finie convenable de k).
Il sagit de se ramener au cas o m = deg P et n = deg Q. Pour cela, on utilise les
formules de la proposition 5.14.
Corollaire 5.21. Soit P Z[X]. Soit Q Z[X]. On note m = deg P , n = deg Q.
Soit p un nombre premier. On note P (resp. Q) limage de P (resp. Q) dans Fp [X].
On suppose que p ne divise pas la fois le coefficient dominant de P et de Q. Alors,
p divise Resm,n (P, Q) si et seulement si P et Q ne sont pas premiers entre eux dans
Fp [X].
Corollaire 5.22. Soit k un corps. Soit P k[X] un polynme de degr n. Alors,
P est sparable si et seulement si Resn,n1 (P, P 0 ) 6= 0, cest--dire que Disc P 6= 0.
Corollaire 5.23. Soit P Z[X] un polynme de degr m. Soit p un nombre
premier. On suppose que p ne divise pas le coefficient dominant de P . On note P
Z/pZ[X] la rduction de P modulo p. Alors, p divise Disc P si et seulement si P est
sparable.

5.4. Exemples
5.4.1. Courbes paramtres : cercle. Les rsultants permettent dliminer
des variables dans des systmes dquations algbriques. Un exemple est celui des
courbes paramtres. Les rsultants permettent de trouver une quation de lensemble
des solutions. Voici un exemple [2, 7.4] :
(
2t
x = 1+t
2
1t2
y = 1+t2
Lensemble des points de la courbe C C2 dont les coordonnes (x, y) peuvent
tre ainsi dcrite pour un paramtre t C sont les couples (x, y) C tels quil existe
t C {i} solution commune des deux quations :

(1 + t2 )x = 2t
(1 + t2 )y = 1 t2

44

CHAPITRE 5. RSULTANTS

Pour t = i, il ny a pas de solutions. Il revient au mme de chercher t dans C{i} ou

dans C tout entier. Pour (x, y) C. On considre les polynmes Px,y = xT 2 2T + x
et Qx,y = (y + 1)T 2 + y 1. Daprs la proposition 5.20, on a quivalence entre
lannulation de Res2,2 (Px,y , Qx,y ) dune part et dautre par que ou bien (x, y) = (0, 1)
ou bien (x, y) 6= (0, 1) et Px,y et Qx,y admettent une racine commune t (cest--dire
(x, y) C). On voit que C ne contient pas (0, 1). Ainsi, C est prcisment form
des (x, y) C2 diffrents de (0, 1) et tels que Res2,2 (Px,y , Qx,y ) = 0.
Plus conceptuellement, on peut considrer P = XT 2 2T + X et Q = (Y + 1)T 2 +
Y 1 comme des lments de A[T ] o A = C[X, Y ]. Soit R = Res2,2 (P, Q) A =
C[X, Y ]. Pour tous (x, y) C2 , le rsultant (2, 2) de Px,y et Qx,y est R(x, y). Ainsi,
C est lensemble des (x, y) C2 {(0, 1)} tels que R(x, y) = 0. Le calcul montre
que R = 4(X 2 + Y 2 1). Donc, C est le cercle unit priv du point (0, 1).
5.4.2. Courbes paramtres : cardiode. On fixe une constante a C . On
considre la courbe paramtre suivante :
(
1t2
x = 2a (1+t
2 )2
4at
y = (1+t
2 )2
On cherche dterminer une quation de cette courbe plane. Un point (x, y) C2
du plan tant donn, la question est de savoir sil existe t C {} vrifiant le
systme dquations ci-dessus, systme que lon peut rcrire sous une forme polynmiale :

x(1 + t2 )2 2a(1 t2 ) = 0
y(1 + t2 )2 4at = 0
(Si on fait t = , on nobtient pas de solutions supplmentaires.) On peut considrer
ces quations comme tant dfinies par lannulation deux polynmes P et Q dans
C[X, Y ][T ]. On peut calculer R = Res4,4 (P, Q) C[X, Y ]. Pour tous (x, y) C, on
a lquivalence entre :
R(x, y) = 0 ;
Les deux polynmes P (x, y), Q(x, y) C[T ] sont tous les deux de degr < 4, ou
il existe t C tel que P (x, y, t) = Q(x, y, t) = 0.
On voit aussitt que P (x, y) et Q(x, y) sont de degr < 4 si et seulement si (x, y) =
(0, 0), et que (0, 0) nappartient pas la courbe paramtre. La courbe est donc
prcisment lensemble des lments (x, y) C2 {(0, 0)} tels que R(x, y) = 0.
Le calcul montre que R = 256a4 (x2 + y 2 ax)2 a2 (x2 + y 2 ) .
5.4.3. Intersection de deux courbes planes. faire en TP.

CHAPITRE 6
LEMME DE HENSEL, BORNE DE MIGNOTTE,
FACTORISATION DANS Z[X]

6.1. Lemme de Hensel

6.1.1. Rsolution dquations.
Lemme 6.1 (Hensel). Soit P Z[X] un polynme unitaire. Soit p un nombre
premier. Soit n 1. Soit x Z tel que P (x) 0 mod pn et que P 0 (x) 6 0 mod p.
Alors, il existe x
Z tel que P (
x) 0 mod p2n et x
x mod pn . En outre, la
2n
classe de congruence de x
modulo p est unique.
On cherche x
sous la forme x
= x + pn y. Le polynme P (x + X) est de la forme
0
P (x) + P (x)X + R(X) o R(X) est un polynmes dont les coefficients de 1 et de X
sont nuls. Par consquent, pour y Z, R(pn y) est multiple de p2n . Ainsi, pour tout
y Z, on a :
P (
x) = P (x + pn y) P (x) + pn yP 0 (x)

mod p2n .

Comme P (x) 0 mod pn , on peut crire P (x) = pn v avec v Z. On a ainsi P (

x) 0
mod p2n si et seulement si v + yP 0 (x) mod pn . Comme p ne divise pas P 0 (x), il existe
z Z tel que zP 0 (x) 0 mod pn . La condition se rcrit y vz mod pn . Ainsi,
x
= x pn vz convient et est lunique solution modulo p2n se rduisant sur x modulo
pn .
Remarque 6.2. En itrant le rsultat du lemme, on obtient facilement quune
solution x de P modulo pn (par exemple dune solution modulo p) telle que p ne
divise pas P 0 (x) se relve de manire unique en une solution modulo pm pour tout
m n.
On peut rinterprter le lemme de Hensel ainsi :
Proposition 6.3. Soit P Z[X] un polynme unitaire. Soit p un nombre premier. Soit x Z tel que p divise P (x) mais ne divise pas P 0 (x). Soit N 1. On
dfinit une suite (xn )nN valeurs dans Z/pN Z en notant x0 la classe de x modulo

46CHAPITRE 6. LEMME DE HENSEL, BORNE DE MIGNOTTE, FACTORISATION DANS Z[X]

pN et la relation de rcurrence :
xn+1 = xn

P (xn )
.
P 0 (xn )

Alors, partir dun certain rang (n log2 N ), la suite xn est constante et P (xn ) = 0
dans Z/pN Z.
Il convient dexpliquer en quoi cet nonc a un sens. Tout dabord, par rcurrence,
on obtient aussitt que pour tout n 0, xn x0 mod p, que P (xn ) P (x0 ) 0
mod p, que P 0 (xn ) 6 0 mod p et quainsi, P 0 (xn ) est inversible dans lanneau Z/pN Z
de sorte que xn+1 a bien un sens. La dmonstration du lemme de Hensel montre que
n
P (xn ) 0 mod p2 . Par consquent, la suite (xn ) devient constante ds que pour
2n N , etc.
On peut rapprocher le lemme du Hensel tel quil est interprt dans la proposition 6.3 de la mthode de Newton :
Soit f : I R une fonction de la classe C 2 dfinie sur un intervalle compact I. On
suppose que f admet un zro x dans cet intervalle et on cherche en dterminer de
bonnes approximations. On choisit un point de dpart x0 I et on dfinit une suite
n)
xn par la formule xn+1 = xn ff0(x
(xn ) (cest la mme formule que plus haut !).
On suppose que la suite (xn )nN est bien dfinie, cest--dire que lon aura toujours
xn I et f 0 (xn ) 6= 0.
Proposition 6.4. Avec les notations et hypothses ci-dessus, si on suppose que
f 0 ne sannule pas sur I (en particulier f 0 (x) 6= 0) et pourvu que x0 ait t choisie
assez proche de x, alors xn converge vers x et, essentiellement, la prcision double
chaque itration.
Daprs la formule de Taylor-Lagrange, pour tout n 0, il existe un I tel que
0 = f (x) = f (xn ) + f 0 (xn )(x xn ) +

f 00 ()
(x xn )2 .
2

En divisant par f 0 (xn ), on obtient :

x xn+1 =

f 00 ()
(x xn )2 .
2f 0 (xn )

Comme f 0 ne sannule pas sur lintervalle compact I, on peut minorer f 0 est valeur
absolue sur I et la valeur absolue f 00 est majore sur I. Il existe donc une constante
C > 0 telle que pour tout n, on ait :
2

|x xn+1 | C |x xn | .
Notons un = log C + log |x xn |, on a un+1 2un . Pourvu que u0 < 0 (cest--dire
|x x0 | < C1 ), un tend vers avec mme un u0 2n , ce qui permet de conclure.

6.2. BORNE DE MIGNOTTE

47

6.1.2. Factorisation.
Lemme 6.5. Soit P Z[X] un polynme unitaire de degr d. Soit p un nombre
premier. Soit n 1. Soit (Q, R) Z/pn Z[X] deux polynmes unitaires de degrs
respectifs q et r tels que si on note P la classe de P dans Z/pn Z[X] on ait P = QR.
On suppose que Res(Q, R) nest pas congru 0 modulo p. Alors, pour tout m n,
il existe duniques polynmes unitaires Q et R dans Z/pm Z[X] de degrs q et r se
rduisant modulo pn sur Q et R tels que lon ait P QR mod pm .
Il sagit bien dune gnralisation de la premire version du lemme de Hensel
puisque la recherche de zros correspond au cas particulier o Q est de la forme
X x ; les hypothses sont cohrentes puisqualors Res(Q, R) = R(x) = P 0 (x).
Comme pour lautre version du lemme de Hensel, il suffit de traiter le cas m = 2n.
et R
dans Z/p2n Z[X] se rduisant sur Q et R
On choisit des polynmes unitaires Q
n
R)
6 0 mod p. Notons
modulo p . On a Res(Q, R) 6 0 mod p, cest--dire Res(Q,
2n

A = Z/p . Le fait que le rsultant de Q et de R soit inversible dans A est quivalent

et de R
soit inversible dans Md (A), cestdemander que la matrice de Sylvester de Q
+V R
A[X]<d
-dire que lapplication qui U A[X]<r et V A[X]<q associe U Q

est un isomorphisme. On considre la diffrence = P QR A[X]<d . Comme

P = QR dans Z/pn Z[X], il vient que les coefficients de sont congrus 0 modulo
pn . Ce qui prcde montre quil existe duniques U et V comme ci-dessus tels que
+V R
A[X]<d et quen outre les coefficients de U et V soient des multiples
= UQ
n
+ V et R = R
+ U . Comme les coefficients de U et V sont
de p . Posons Q = Q
n
R
+ UQ
+V R
=
multiples de p , on a U V = 0 dans A[X], ce qui montre que QR = Q

QR + = P , ce qui montre lexistence de Q et R, lunicit se montrant de manire

similaire.
Remarque 6.6. Si on implmente lide de la dmonstration pour appliquer plusieurs fois le calcul, on a intrt garder en mmoire une relation de Bzout ,
cest--dire des polynmes A et B de degrs appropris tels que AQ + BR = 1 et
de chercher dterminer non seulement Q et R vrifiant des congruences modulo
une puissance double de p mais aussi chercher A et B tels que AQ + BR = 1 en
modifiant des relvements arbitraires de A et de B. Pour n = 1, on peut utiliser
lalgorithme dEuclide tendu pour obtenir la relation de Bzout.
6.2. Borne de Mignotte
Dfinition 6.7. Soit P p
= a0 + a1 X + C[X]. On pose kP k = maxi |ai |,
P
P
Qn
2
kP k1Q= i |ai | et kP k2 =
k=1 (X zk ), on pose M (P ) =
i |ai | . Si P = an
n
|an | k=1 max(1, |zk |) (si P = 0, on pose M (P ) = 0).
P
P
Thorme 6.8 (Mignotte). Soit P = i ai X i C[X]. Soit Q = i bi X i
C[X]. On note n = deg P , m = deg Q. On suppose que Q divise P . Alors,
 
 bm 
kQk kQk1 2m M (Q)   2m kP k2 .
an

48CHAPITRE 6. LEMME DE HENSEL, BORNE DE MIGNOTTE, FACTORISATION DANS Z[X]

Corollaire 6.9. Soit P Z[X]. Soit Q Z[X]. On suppose que Q divise P dans
Z[X]. Alors,
kQk 2deg Q kP k2 .
 
 
En effet, avec les notations du thorme 6.8, bm divise an , donc  bamn  1.
Remarque 6.10. Si P et Q sont des lments de C[X], on a M (P Q) =
M (P )M (Q).
Un des ingrdients importants de la dmonstration du thorme 6.8 est le suivant :
Thorme 6.11 (Landau). Soit P C[X]. Alors, M (P ) kP k2 .
Lemme 6.12. Soit P C[X]. Soit z C. k(X z)P k2 = k(zX 1)P k2 .
P
On peut crire P = iZ ai X i . Le coefficient de X i dans (Xz)P (resp. (zX1)P )
est ai1 zai (resp. zai1 ai ).
On en dduit dune part :
X
2
k(X z)P k2 =
[(ai1 zai )(ai1 zai ]
i

|ai1 | + |z|

|ai | z

(1 + |z| ) kP k2 z

ai ai1 z

ai ai1 z

ai1 ai

ai1 ai ,

et dautre part :
2

k(zX 1)P k2

[(zai1 ai )(zai1 ai ]

i
2

= |z|

|ai1 | +

|ai | z

i
2

(1 + |z| ) kP k2 z

ai ai1 z

X
i

ai ai1 z

ai1 ai

ai1 ai ,

ce qui permet de conclure.

Dmontrons le thorme de Landau. On peut supposer que P est unitaire, et crire
P = (X z1 ) . . . (X zk )(X u1 ) . . . (X ul ) o les racines complexes de P vrifient
|zi | > 1 et |ui | 1. Notons Q = (X z1 ) . . . (X zk )(u1 X 1) . . . (ul X 1). En
appliquant l fois le thorme de Landau, on obtient que kP k2 = kQk2 . On peut
2
conclure en utilisant lingalit vidente kQk2 |Q(0)| = |z1 . . . zk | = M (P ).
Dmontrons le thorme de Mignotte. On peut supposer que P et Q sont unitaire.
Lingalit kQk kQk1 est vidente. Montrons maintenant lingalit M (Q)
kP k2 . Notons R le polynme unitaire tel que P = QR. On a videmment M (R)
1, do M (P ) = M (Q)M (R) M (Q). Daprs le thorme de Landau, il vient

6.3. FACTORISATION DANS Z[X] ET Q[X]

49

M (Q) M (P ) kP k2 . Il reste
lingalit kQk1 2m M (Q). On peut crire
P tablir
i
Q = (X z1 ) . . . (X zm ) = i bi X . Pour tout 0 i m, on a
X
Y
(1)i bmi =
zj .
J{1,...,m},#J=i jJ


Il en rsulte que |bmi |
kQk1 =

X
i

m
i


, do

|bmi |

!
X m 
M (Q) = 2m M (Q) .
i
i

6.3. Factorisation dans Z[X] et Q[X]

On commence par un algorithme de factorisation pour des polynmes unitaires
coefficients entiers et sans facteur carr (autrement dit, en tant qulment de Q[X],
P est sparable, ou encore Disc P 6= 0).
Algorithme de factorisation dans Z[X] 6.13. Soit P Z[X]. On suppose
que P est unitaire et que Disc P 6= 0. On va dterminer la factorisation de P dans
Z[X] en produits de polynmes unitaires irrductibles.
On choisit un nombre premier p ne divisant pas Disc P . On dtermine un entier
M 1 tel que M 2deg P kP k2 , puis un entier d 1 tel que pd 2M + 1.
On dtermine la factorisation Q1 . . . Qk dans Fp [X] de la rduction modulo p de P
en utilisant lalgorithme de Berlekamp (les Qi Fp [X] sont irrductibles et unitaires).
En utilisant le lemme de Hensel, on dtermine Q1 , . . . , Qk Z/pd Z[X] unitaires
se rduisant sur les Qi modulo p et tels que si on note P la rduction de P modulo
pd , on ait P = Q1 . . . Qk .
Pour toute partie I {1, . . . , k} de cardinal compris entre 1 et k 1, on calcule
I = Q Qi Z/pd . On note QI Z[X] un reprsentant (unitaire) de QI tel
Q
iI
j k
que kQI k

pd
2

. On teste si QI divise P , si oui, on a dtermin un facteur non

trivial de P dans Z[X] (et si aucun QJ pour J contenu strictement dans I ne vrifie
dj cela, alors QI est irrductible et on peut continuer examiner les parties de
{1, . . . , k} contenues dans le complmentaire de I pour dterminer les autres facteurs
irrductibles).
Si aucun polynme QI ne fournit un facteur non trivial de P , alors P Z[X] est
irrductible.
Remarquons que lhypothse selon laquelle p ne divise pas Disc P fait que la rduction de P modulo p est un polynme sparable ; lalgorithme de Berlekamp sapplique
lui et les hypothses du lemme de Hensel seront aussi satisfaites. Manifestement, si
lalgorithme dcrit ci-dessus termine en renvoyant un facteur non trivial de P dans
Z[X], ce rsultat est juste. Pour conclure, il faut montrer inversement que si Q Z[X]
est un diviseur non trivial (que lon peut supposer unitaire) de P , alors il existe une
partie I telle que Q = QI . La borne de Mignotte nous dit que si on tel polynme Q
existe, alors ses coefficients sont plus petits que M en valeur absolue ; en particulier,

50CHAPITRE 6. LEMME DE HENSEL, BORNE DE MIGNOTTE, FACTORISATION DANS Z[X]

dans Z/pd Z[X]. Si on rduit Q

modulo p, on
il suffit de connatre sa rduction Q
Q
obtient ncessairement un sous-produit iI Qi de la factorisation Q1 . . . Qk de P
modulo p pour une partie I de {1, . . . , k} (de cardinal diffrent de 0 et k). Daprs
= Q Qi = QI .
lunicit du rsultat dans le lemme de Hensel, on doit avoir Q
iI
Il reste expliquer comment utiliser lalgorithme 6.13 pour factoriser dans Z[X]
et Q[X]. Tout dabord, pourvu que lon sache factoriser dans Z, le problme de la
factorisation dans Z[X] et dans Q[X] sont essentiellement quivalents. Comme dans
le cas des polynmes coefficients dans Fq [X], pour factoriser dans Q[X], on peut
supposer que le polynme est sans facteurs carrs (cest--dire sparable), autrement
dit que le discriminant du polynme est non nul. On sest ramen la factorisation de
P Q[X] unitaire et sparable. Pour appliquer lalgorithme 6.13, il reste montrer
que lon peut supposer que P Z[X]. On utilise le lemme suivant :
Lemme 6.14. Soit P Q[X] un polynme unitaire. Il existe un entier n 1 tel
que ndeg P P ( n1 X) appartienne Z[X].
P
P
1
di i
i
d
X = Xd +
Si P =
i ai n
i ai X et d = deg P , on obtient n P ( n X) =
nad1 X d1 + n2 ad2 X d2 + + nd a0 . Il est vident que lon peut trouver un entier
n 1 convenable.
Le problme de la factorisation dans Q[X] de P et de P ( n1 X) tant quivalents,
on peut effectivement se ramener la situation de lalgorithme 6.13.

CHAPITRE 7
RSIDUS QUADRATIQUES

7.1. Symbole de Legendre

 
Dfinition 7.1. Soit p un nombre premier impair. Soit a Z. On dfinit ap
 
 
{1, 0, 1} de la faon suivante. Si p divise a, on pose ap = 0. Sinon, on pose ap = 1
 
a
si la classe de a dans F
p est un carr, et
p = 1 sinon.
videmment,

 
a
p

ne dpend que de la classe de a modulo p.

Proposition 7.2. Soit p un nombre premier impair. Soit a Z. On a la

congruence suivante :
 
p1
a
a 2
mod p .
p
Si p divise a, le rsultat est vident. On peut donc supposer que limage a de a

dans Fp est dans F

p . Le groupe Fp est cyclique dordre (pair) p 1. Notons en
un gnrateur. Tout lment de F
scrit de manire unique sous la forme i
p p1 2
p1
pour 0 i p 2. Observons que 2
= p1 = 1. Comme 2 6= 1, on a
p1

p1

2 = 1. Il en rsulte que si a = i , alors a 2 = (1)i . Par ailleurs, il est clair

que i est un carr dans F
p si et seulement si i est pair, ce qui permet de conclure.
Corollaire 7.3. Soit p un nombre premier impair. Soit (a, b) Z2 .
    
a
b
ab
=
.
p
p
p
Corollaire 7.4. Soit p un nombre premier impair. Alors, 1 est un carr modulo
p si et seulement si p est congru 1 modulo 4.

52

CHAPITRE 7. RSIDUS QUADRATIQUES

Thorme 7.5 (Loi de rciprocit quadratique). Si p et q

nombres premiers impairs distincts, on a :
 
 
p1 q1
q
p
= (1) 2 2
.
q
p

sont deux

En outre, si p est un nombre premier impair, alors

 
p2 1
2
= (1) 8 .
p

7.2. Symbole de Jacobi

k
1
Dfinition 7.6. Soit n un entier naturel impair. On crit n = p
1 . . . pk o les
pi sont des

nombres premiers (impairs). Pour tout a Z, on dfinit le symbole de
Jacobi na par la formule :
 k
 a   a 1
a
=
...
.
n
p1
pk

Le symbole de Jacobi gnralise le symbole de Legendre, cest pourquoi on utilise la

mme notation.
Proposition 7.7. Le symbole de Jacobi est multiplicatif en les deux variables :
   0

 m  m m
m
mm0
m
=
,
=
,
n
n
n
nn0
n
n0
pour m, m0 des entiers et n, n0 des entiers impairs.
 
La premire formule rsulte de la multiplicativit du symbole de Legendre
p
pour tout nombre premier impair. La deuxime dcoule aussitt de la dfinition.


Proposition 7.8. Soit m Z. Soit n un entier naturel impair. Alors m
n = 0 si
et seulement si m et n ne sont pas premiers entre eux.
 


Manifestement, m
= 0 si et seulement si m
= 0 pour un nombre premier p
n
p
divisant n, cest--dire quun nombre premier divisant n divise m.
Thorme 7.9 (Loi de rciprocit quadratique). Si m et n sont entiers naturels impairs, on a :
m
n
m1 n1
= (1) 2 2
.
n
m
En outre, si n est un nombre impair, alors
 


n2 1
n1
2
1
= (1) 8 ,
= (1) 2 .
n
n

7.2. SYMBOLE DE JACOBI

53

Notons : Z/4Z Z/2Z le morphisme de groupe envoyant [1] sur 0 et [1] sur 1.
Pour a 1+2Z, on note encore (a) = (a mod 4). Si a et b sont deux entiers relatifs
impairs, on a donc (ab) = (a)+(b). On vrifie aussitt que pour tout a 1+2Z, on
se ramne aussitt au cas o a = 1. Montrons la
a (a) = a1
2
mod 2, puisque lon


(m)(n) n
formule m
=
(1)
pour
n et m impairs
positifs.
On peut supposer que
n
m




m
n
m et n sont premiers entre eux puisque sinon n = m = 0. On crit m = p1 . . . pk
et n = q1 . . . ql o les pi et les qj sont des nombres premiers impairs. On a :
m Y p 
i
=
.
n
q
j
i,j
 
 
q
Daprs le thorme 7.5, qpji = (1)(pi )(qj ) pji , do
m
n
P
= (1) i,j (pi )(qj )
.
n
m
On a bien sr :

!
X
X
X
(pi )(qj ) =
(pi )
(qj ) = (m)(n) ,
i,j

ce qui permet de conclure.

La formule 1
= (1)(n) sobtient de mme partir du cas o n est premier.
n
2
Notons de mme pour tout n 1+2Z, (n) la classe de n 81 dans Z/2Z. se factorise en une application Z/8Z Z/2Z qui est un morphisme de groupes ((1) = 0,
(3) = 1). Ainsi,
(mn) = (m) + (n), do (1)(mn) = (1)(m) (1)(n) . Bref,


2
la formule n = (1)(n) se ramne au cas o n est un nombre premier impair.


On peut utiliser le thorme 7.9 pour calculer efficacement m
n (notamment sans
avoir factoriser m et n et calculer les symboles de Legendre correspondants) :
Algorithme de calcul du symbole de Jacobi 7.10. Soit m
Z. Soit n un
nombre entier impair positif. Cet algorithme calcule rcursivement m
n .
Si n = 1, on renvoie 1.
Sinon, on calcule a = m mod n.
Si a = 0, on renvoie 0.
 0
Si a est pair, on peut poser a0 = a2 . On calcule rcursivement an et on renvoie
 0
(1)(n) an .




Si a est impair, on calcule rcursivement na et on renvoie (1)(a)(n) na .


m
Montrons par rcurrence sur n (impair) que lalgorithme
de
calcul
de
termine.
n
 0
m
Si n = 1, on a un cas de terminaison. Supposons que n0 termine pour tout m0 Z et


n0 impair infrieur strictement n. Pour montrer que m
supposer
n termine, on peut


n
que m = a et que 0 < a < n. Si a est impair, on calcule rcursivement a , qui termine
par hypothse de rcurrence puisque a < n. Tout entier 1 a < n peut scrire de
manire unique sous la forme 2i b. avec b impair et i 0. On vient de traiter le cas

54

CHAPITRE 7. RSIDUS QUADRATIQUES

a
n

i = 0. Par rcurrence immdiate sur i, le calcul de

que le rsultat renvoy par lalgorithme est le bon.

termine. On montre de mme

7.3. Dmonstration de la loi de rciprocit quadratique

Il existe plusieurs centaines de dmonstration de la loi de rciprocit quadratique
(thorme 7.5).
7.3.1. Zolotarev. On en prsente ici une dmonstration dont le principe est d
Zolotarev (1872).
On rappelle que pour toute permutation dun ensemble fini X, on peut dfinir
sa signature ().
Proposition 7.11. Soit p un nombre premier
  impair. Soit a un nombre entier
non multiple de p. Alors, le symbole de Legendre ap est la signature de la permutation
de Fp induite par la multiplication par limage a de a dans F
p.
On rappelle que si est une permutation de {0, . . . , n 1}, alors on a lgalit
suivante dans Q :
Y
(j) (i)
() =
.
ji
0i<jn1

Appliquons ceci la permutation de {0, . . . , p 1} qui i associe ai mod p et

chassons les dnominateurs :
Y
Y
()
(j i) =
((j) (i)) .
0i<jp1

0i<jp1

On peut raisonner modulo p ; comme (j) (i) a(j i) mod p, il vient :

Y
Y
p(p1)
()
(j i) a 2
(j i) mod p .
0i<jp1

0i<jp1

On peut diviser par j i mod p pour 0 i < j p 1 puisque p est premier :

() a

p(p1)
2

mod p .

Daprs le petit thorme de Fermat, a a mod p, do :

() a

(p1)
2

mod p .

On peut conclure puisque les deux nombres comparer sont 1.

Proposition 7.12. Soit p un nombre premier impair. Alors,
Notons k =

p1
2 .

Daprs la proposition 7.11,

{0, . . . , 2k} qui i associe 2i mod p.


0 1 2 ... k
=
0 2 4 . . . 2k

k+1
1

 
2
p

k+2
3

 
2
p

= (1)

p2 1
8

est gal la permutation de

...
...

2k
2k 1


.

7.3. DMONSTRATION DE LA LOI DE RCIPROCIT QUADRATIQUE

55

Bref, les couples (a, b) de {0, . . . , p 1} tels que a < b et (a) > (b) (cest--dire les
inversions de ) sont les couples (i, k + j) avec 1 i k, 1 j k et i j. Il y en
2
a k(k+1)
= p 81 , ce qui permet de conclure.
2
Dmontrons la loi de rciprocit quadratique. On se donne p et q deux nombres
premiers impairs. Notons X = {0, . . . , p1}{0, . . . , q 1}. On dfinit trois bijections

1 , 2 , 3 : X Z/pqZ de sorte que pour 0 i < p et 0 j < q, on ait :

1 (i, j) = i + pj , 2 (i, j) = qi + j , 3 (i, j) = qi + pj .
Pour (a, b) {1, 2, 3}2 , notons a,b la permutation a1 b de {0, . . . , p 1}
{0, . . . , q 1}, cest--dire que lon a la relation a a,b = b . On obtient aussitt que
1,3 (i, j) = (qi mod p, (qi div p + j) mod q). En effet, si (i, j) X, par dfinition,
si on dtermine (i0 , j 0 ) X tel que 3 (i, j) = 1 (i0 , j 0 ), alors 1,3 (i, j) = (i0 , j 0 ). Ici, la
relation cherche est qi + pj i0 + pj 0 mod pq. Calculons (1,3 ). On a la relation
1,3 = o et sont les permutations de X dfinies par (i, j) = (qi mod p, j)
et (i, j) = (i, (i) + j mod q) o (i) = qi div p. On a donc (1,3 ) = ()(). Tout
dabord, () = 1. En effet, sur chaque tranche {i} {0, . . . , q 1}, sidentifie
laddition avec laddition avec (i) modulo q. Laddition avec 1 modulo q sur Z/qZ
est un q-cycle, sa signature est donc 1 puisque q est impair. Ceci implique aussi
que laddition avec (i) modulo q est de signature 1, puis que () = 1. Calculons
maintenant (). On raisonne cette fois-ci sur les tranches {0, . . . , p 1} {j} : y
induit la
avec q modulo p. En utilisant la proposition 7.11, il vient que
q  
 multiplication
q
q
() = p = p .
 
 
Finalement, (1,3 ) = pq . De mme, (2,3 ) = pq . On a la formule 1,3 =
1,2 2,3 . La loi de rciprocit quadratique se ramne donc au calcul de (1,2 ). On
identifie Z/pqZ Y = {0, . . . , pq 1}. Les formules dfinissant 1 et 2 dfinissent
en fait directement des lments de Y . On a bien sr (1,2 ) = (2 11 ) o 2 11
est une permutation de Y . Calculons le nombre dinversions N de 2 11 cest--dire
le nombre de couples (i, j), (i0 , j 0 ) dlments de X tels que 1 (i, j) < 1 (i0 , j 0 ) mais
2 (i, j) > 2 (i0 , j 0 ), cest--dire que i + pj < i0 + pj 0 et qi + j > qi0 + j 0 , ou encore
p(p1) q(q1)
q(q1)
2
i0 < i et j < j 0 . Do, N = p(p1)
. Bref, (1,2 ) = (1) 2
. Comme p
2
2
et q sont impairs, il vient (1,2 ) = (1)

(p1) (q1)
2
2

, ce qui achve la dmonstration.

7.3.2. Sommes de Gauss. La dmonstration qui suit utilise des sommes de

Gauss et est tire de [?].
 
Commenons par lnonc p2 = (1)(p) pour p premier impair. Il existe une
extension finie K de Fp contenant un lment tel que 4 = 1, cest--dire que
1
est une racine primitive huitime de lunit dans K. On considre y = + 
. Il
2
2
vient que y = 2. Les racines carres de 2 dans K sont y et y. On a ainsi p = 1
si et seulement si y Fp cest--dire que y p = y. Or, y p = p + p . La quantit
i + i ne dpend que de i modulo 8 et est invariante si on change
  i en i. Par
p
consquent, si p est congru 1 modulo 8, on a bien y = y et p2 = 1. Sinon, p

56

CHAPITRE 7. RSIDUS QUADRATIQUES

est congru 5 ou 3 modulo 8 1 modulo 8, alors y p = y. En utilisant la relation

4 = 1, on obtient 5 + 5 = (+1 ) = y 6= y. On peut ainsi conclure que

si p est congru 3 modulo 8, alors p2 = 1.

On fixe maintenant deux nombres premiers impairs distincts p et `. Il existe une extension finie K de Fp contenant une racine primitive `-ime de lunit w. On considre
la somme de Gauss :
X x
y=
wx .
`
xF`

La quantit wx a bien un sens pour x F` puisque w` = 1.

Lemme 7.13. Dans K, on a lgalit :
y 2 = (1)(`) ` .
On dveloppe le produit :
y2

 xz 

(x,z)F2`

X
uF`

wx+z

!
X  x(u x) 
wu
`

xF`

Le terme correspondant x = 0 sont nuls. On ne garde que ceux pour lesquels

x 6= 0, de faon pouvoir faire une division :

  2
 




x(u x)
x
1 ux1
1
1 ux1
1 ux1
(`)
=
=
= (1)
.
`
`
`
`
`
`


P
P
1
, de sorte que y 2 = (1)(`) uF` Cu wu .
Pour u F` , notons Cu = xF 1ux
`
`

1
On a bien
P sr C0z
= ` 1. Pour u 6= 0, les lments 1 ux parcourent F` {1}.
Comme zF` ` = 0, on a Cu = 1 pour u 6= 0. Il vient ainsi :

Cu wu = ` 1

`1
X

wu = ` .

u=1

uF`

Cette galit permet de conclure.

Lemme 7.14. y p1 = p` .
On fait les calculs dans K qui est de caractristique p. Llvation la puissance p
est un automorphisme de corps.
X x
yp =
wpx .
`
xF`

On fait le changement de variable z = px dans F` :

 1 
p
X  zp1 
p
p
z
y =
w =
y=
y.
`
`
`
xF`

57

7.3. DMONSTRATION DE LA LOI DE RCIPROCIT QUADRATIQUE

En divisant par y (qui nest pas nul daprs le calcul prcdent), on obtient le rsultat.


On obtient le rsultat en calculant de deux manires y p1 . Dune part y p1 = p` ,
 

p1
p1
dautre part y p1 = y 2 2 = (1)(`)(p) ` 2 = (1)(`)(p) p` .
7.3.3. Rsultants.
Proposition
7.15. Soit A un anneau. Tout polynme de Laurent P =
Pn
i
1
tel que ai = ai pour tout i scrit de manire unique
i=n ai X A[X, X
1
sous la forme Q(X + X ) avec Q A[X].
1
Si Q = b0 +b1 X + +bn X n , alors Q(X + X
) = bn X n + +bn X n , ce qui permet
1
dobserver que si Q nest pas nul, alors Q(X + X
) non plus. Ceci montre lunicit de
Q.
Montrons maintenant lexistence. On procde par rcurrence sur le degr. Si P =
a0 , Q = a0 convient. Supposons le rsultat connu pour des polynmesP
de Laurent
n
faisant intervenir des exposants compris entre (n1) et n1. Soit P = i=n ai X i
1 n
avec ai = ai . Le polynme de Laurent P an (X + X ) a des coefficients symtriques
1 n
) =
et par hypothse de rcurrence, il existe un polynme R tel que P an (X + X
1
1
n
R(X + X ). Le polynme Q = R + an X vrifie P = Q(X + X ).

Dfinition 7.16. Pour p un nombre premier impair, on note Vp Z[X] le polyP p1

1
i
2
) = i=
nme tel que Vp (X + X
p1 X .
2

Proposition
7.17. Si p et q sont deux nombre premiers impairs distincts, on a
 
q
p1 q1 (Vp , Vq ).
,
p = Res
2

Montrons que ces deux quantits sont congrues modulo p.

Lemme 7.18. Vp est congru (X 2)

p1
2

modulo p.

Le classe Vp de Vp dans Fp [X] est un polynme unitaire de degr p1

2 . Pour montrer
p1
que Vp = (X 2) 2 , il suffit de montrer que si K est un corps de dcomposition de Vp
sur Fp , alors 2 est lunique racine de Vp dans K. Soit x K tel que Vp (x) = 0. Dans
une extension finie convenable L de K, il existe tel que x = + 1 ( est solution de
P p1
i
2
lquation du second degr 2 x +1 = 0.) On a Vp (x) = Vp ( + 1 ) = i=
p1 = 0.
2

Il en rsulte que p = 1, bref, ( 1)p = 0, do = 1 et x = 2.

La classe de congruence modulo p de Res(Vp , Vq ) est Res(Vp , Vq ) calcul dans
 Fp ,
p1
p1
2
2
cest--dire Vq (2)
, ou encore q
, dont on sait quil est congru modulo p pq .
Pour conclure, il reste montrer que Res(Vp , Vq ) est gal 1. Pour cela, il suffit
de montrer que pour tout nombre premier `, ` ne divise pas Res(Vp , Vq ), cest--dire
que Vp et Vq nont pas de racine commune dans une extension finie K de F` . Soit
x K une racine commune de Vp et Vq dans K. Comme prcdemment, on peut
crire x = + 1 avec appartenant une extension L de K. Vp (x) = 0 implique

58

CHAPITRE 7. RSIDUS QUADRATIQUES

p = 1 et Vq (x) = 0 implique q = 1. Comme p et q sont premiers entre eux, on

obtient = 1. Quitte changer les rles de p et q, on peut supposer que p 6= `, on a
P p1
i
2
alors Vp (x) = i=
p1 = p qui est non nul puisque p 6= `.
2
 
Corollaire 7.19. Si p et q sont deux nombres premiers impairs distincts, pq =
 
p1 q1
(1) 2 2 pq .
Cela rsulte de la formule liant Res(Vp , Vq ) et Res(Vq , Vp ).
7.4. Test de primalit de Solovay-Strassen
Test de primalit probabiliste de Solovay-Strassen, 1977/1978 7.20
Soit n 3 un entier
un nombre entier 2 a

naturel impair. On tire au hasard


n 1. On calcule na (cf. algorithme 7.10). Si na = 0, on rpond que n nest pas




n1
n1
premier. Sinon, on calcule na et a 2 mod n, si on trouve na a 2 mod n, on
rpond que n est probablement premier, sinon on rpond que n nest pas premier.
Compte tenu de ce qui prcde, il est vident que si n est premier, cet algorithme
va dire que n est probablement premier. Si n nest pas premier, lalgorithme peut
rpondre soit que n nest pas premier (auquel cas il a raison) soit que n est probablement premier. Nous allons montrer que si n non premier est fix, la probabilit de
tomber sur un a mettant en vidence que n nest pas premier est au moins 12 . Ainsi,
si on fait le test avec k entiers choisis indpendamment entre 1 et n 1, la probabilit
de dtecter que n nest pas premier est au moins 1 21k .
Proposition 7.21. Soit n 3 un entier impair non premier. Pour au moins la
moiti des a compris entre 1 et n 1, le test ci-dessus dtecte la non-primalit de n.


n1
Lensemble des 1 a n 1 tels que a n = 1 et que na a 2 mod n
(cest--dire tels que le test choue dtecter la non-primalit de n) sidentifie au
sous-groupe suivant de Z/nZ :
n
a
o
n1
G = a Z/nZ ,
a 2
mod n .
n
Le cardinal de G est (n)
o e est lindice de G dans Z/nZ . Si on montre e 2, le
e
cardinal de G sera manifestement infrieur n1
2 , et le test dtectera la non-primalit
de n avec une probabilit 12 . Pour montrer que e 2, il suffit de montrer que
e 6= 1, cest--dire que G 6= Z/nZ . Supposons par labsurde que G = Z/nZ et
dduisons-en une contradiction.
n est sans facteur carr. Montrons que lon a alors

Commenons par le cas o
a

=
1
pour
tout
a

Z/nZ
.
On peut crire n = rs avec r 3 et s 3 premiers
n
n1
n1
entre eux. Par hypothse, si an = 1, on a a 2 1 mod n. En fait, on a a 2 1
n1
mod n. En effet, si on a un tel a vrifiant a 2 1 mod n, on peut trouver, daprs
le lemme chinois un b Z/nZ tel que b 1 mod r et b a mod s. On a alors
 
n

b 1 2 congru 1 modulo r, 1 modulo s, mais comme il est aussi congru

b
p

7.4. TEST DE PRIMALIT DE SOLOVAY-STRASSEN

59

 
modulo rs, on doit avoir pb = 1 = 1, contradiction. Ainsi, pour tout a Z/nZ ,


on a na = 1, ce qui nest pas possible.
Notons p un nombre premier divisant n et crivons
n = pq. Les entiers impairs p
 
a
et q sont premiers entre eux. Il existe a tel que p = 1. Daprs le lemme chinois,
on peut trouver
un entier b congru a modulo p et 1 modulo q. On obtient aussitt

 

que na = ap 1s = 1, ce qui conduit une contradiction
Il reste traiter le cas o n admet un facteur carr. On peut crire n = pe q o
p est un nombre premier ne divisant pas q et e 2. Lhypothse implique que pour
tout a Z/nZ , on a an1 = 1 dans Z/nZ . Autrement dit, lexposant de Z/nZ
divise n 1. Comme Z/nZ ' Z/pe Z Z/qZ , lexposant de Z/pe Z divise aussi
n 1. Daprs le lemme suivant, cela implique que pe1 divise n 1. Par consquent
p divise n 1, contradiction.
Lemme 7.22. Soit p un nombre premier impair. Soit e 2. Le sous-groupe H
de Z/pe Z form des lments congrus 1 modulo p est cyclique de cardinal pe1 ,
engendr par la classe de tout lment de la forme 1 + pa avec p ne divisant pas a.
Lemme 7.23. Soit p un nombre premier impair. Soit i 1. Soit a un nombre
entier non multiple de p. Alors, il existe un entier b non multiple de p tel que (1 +
pi a)p = 1 + pi+1 b.
On dveloppe (1 + pi a)p en utilisant la formule du binme, modulo pi+2 :
(p 1) 2i+1 2
p
a mod pi+2
2
est nul modulo pi+2 , ce qui donne :

(1 + pi a)p 1 + pi+1 a +
Le terme faisant intervenir p2i+1

(1 + pi a)p 1 + pi+1 a mod pi+2 ,

ce qui permet de conclure.
e2

Par rcurrence, si p ne divise pas a, (1 + pa)p

peut scrire 1 + pe1 b avec p ne
divisant pas b, ce qui montre que lordre de la classe de 1 + pa est dordre exactement
pe1 dans le groupe H.
Remarque 7.24. En 2002, Manindra Agrawal, Neeraj Kayal et Nitin Saxena ont
trouv un test de primalit utilisant en O((log2 n)12+ ) oprations lmentaires pour
tout > 0.

CHAPITRE 8
FACTORISATION DENTIERS, CRYPTOSYSTME RSA

tant donn un entier naturel n 2 qui nest pas premier, on cherche dterminer
p > 1 et q > 1 tels que n = pq. On prsente ici lalgorithme de Pollard.

8.1. Algorithme de Pollard

Algorithme de Pollard 8.1. Soit n 4 un entier naturel. On choisit au hasard x0 {0, . . . , n 1}. On dfinit une suite rcurrente dans {0, . . . , n 1} par
xi+1 = x2i 1 mod n.
Si on trouve deux indices i < j tels que que d = pgcd(xj xi , n) soit un diviseur
non trivial de n, on renvoie d, sinon on renvoie chec .
Il faut expliquer comment dterminer efficacement de tels indices i < j sil en
existe. Une manire de reformuler le problme consiste dire que lon cherche une
cycle de la suite xn mod p pour un certain nombre premier p (inconnu) divisant
n qui ne soit pas un cycle de xn mod n.
Une mthode de dtection de cycles peut tre dduite de la proposition suivante :
Proposition 8.2. Soit f : X X une fonction. Soit (xn ) une suite dans X
vrifiant xn+1 = f (xn ). Sil existe deux indices i < j tels que xi = xj , alors il existe
n > 0 tel que x2n = xn et i n j.
Posons k = j i. Pour m i, xm ne dpend que de la classe de m dans Z/kZ.
Prenons pour n le plus petit multiple de k suprieur ou gal i. Les entiers n et 2n
sont congrus modulo k et suprieurs ou gaux i, on a donc x2n = xn .
Pour trouver un cycle, il suffit donc de calculer, pour tout entier n, xn et x2n :
Algorithme de dtection de cycles 8.3. Soit f : X X. Soit x0 X. On
pose n = 0, x = x0 , y = y0 . On fait n := n + 1, x := f (x), y := f (f (x)), jusqu ce
que y = x. On renvoie (n, x).
Une premire implmentation de lalgorithme de Pollard est la suivante :

62

CHAPITRE 8. FACTORISATION DENTIERS, CRYPTOSYSTME RSA

pollard:=proc(n)
local x,y,d;
begin
x:=random(0..n-1)();
y:=x;
i:=0;
while TRUE do
x:=x^2-1 mod n;
y:=(y^2-1)^2-1 mod n;
d:=igcd(x-y,n);
if (1<d) and (d<n) then return(d);end_if;
if d=n then return(FAIL);end_if;
end_while;
end_proc
Exemple 8.4. n = 91 = 7 13, x0 = 2.
Le principe heuristique de lalgorithme est quon espre que si n = pq avec p et q
premiers entre eux, les comportements des suites xn mod p et xn mod q vont tre
indpendants. En particulier, si on dtecte un cycle modulo p, on espre ne pas tomber
par hasard aussi sur un cycle modulo q, de sorte que ce cycle fournit une factorisation
non triviale de n. Pour donner une estimation du coup en temps partir de lnonc
suivant :

Proposition 8.5. Soit n 1 un entier. Soit k un entier tel que k 1 + 2n.

Alors, une fonction f : {1, . . . , k} {1, . . . , n} choisie alatoirement (et uniformment) a une probabilit 21 dtre injective.
n!
et le nombre de fonctions consiLe nombre de telles fonctions injectives est (nk)!
k
dres est n . La probabilit que f soit non injective est donc :

p = 1 (1

1
2
k1
) (1 ) (1
).
n
n
n

On utilise lingalit 1 x ex pour tout x R :

p e
Si k 1 +

2n, on a p

1
e

Pk1

i
i=0 n

= e

k(k1)
2n

12 .

Dans lalgorithme de Pollard, on peut esprer un coup en temps (en considrant

1
les oprations modulo n comme lmentaires) delordre de n 4 . En effet, si p est le
plus petit nombre premier divisant n (donc p n), la suite des xn mod p devrait

probablement prsenter une rptition ds les O( p) premires valeurs.

8.2. CRYPTOGRAPHIE CLEF PUBLIQUE

63

8.2. Cryptographie clef publique

8.2.1. Principe. Le principe est le suivant. Alice cre une clef publique PA et
une clef prive SA . Chaque clef dfinit une fonction X X o X est un certain
ensemble fini. Alice rend la clef PA publique mais garde secrte la clef SA .
Si Bob veut envoyer un message Alice sous la forme dune suite dlments de X,
il applique PA chaque lment x de son message, et envoie les rsultats y = PA (x)
Alice. Alice applique SA ces y.
Bien sr, il faut que pour tout x X, SA (PA (x)) = x, cest--dire que SA et PA
sont des fonctions inverses lune de lautre. Pour que cela entre dans le domaine de la
cryptographie, il faut quil soit trs difficile de dterminer la fonction SA connaissant
la fonction PA . Il ne faut pas quun espion ayant accs aux donnes transmises par
Bob Alice puisse dcoder le message, seule Alice doit pouvoir le faire.
8.2.2. Le cryptosystme RSA. Dcrivons les ensembles X, les clefs PA et SA ,
et les fonctions PA () et SA () associes.
Alice choisit deux grands nombres entiers distincts p et q, pose n = pq. Lensemble
X sera Z/nZ.
On a (n) = (p 1)(q 1). Alice, choisit un entier naturel d premier avec (n)
et dtermine un entier naturel e inverse de d modulo (n) (cf. algorithme dEuclide
tendu).
La clef publique PA est le couple (e, n) et la clef prive SA est (d, n).
La fonction PA () : Z/nZ Z/nZ est a 7 ae et de mme la fonction
SA () : Z/nZ Z/nZ est a 7 ad .
Proposition 8.6. Avec les notations ci-dessus, pour tout a Z/nZ, on a ade = a,
autrement dit SA (PA (a)) = a pour tout a X, mais aussi PA (SA (a)) = a.
On peut crire ed = 1+k(p1)(q1) avec k Z. Soit a Z. Montrons que ade a
mod p. Si a 0 mod p, cest vident. Sinon, ap1 1 mod p, do ak(p1)(q1)

k(q1)
ap1
1 mod p, finalement ade a mod p. De mme, ade a mod q.
Daprs le lemme chinois, ade a mod pq.
Il reste expliquer pourquoi il est raisonnable de penser quil est difficile de dcoder
un message cod avec RSA :
Proposition 8.7. Soit n un entier de la forme pq avec p et q premiers distincts.
Les deux problmes suivant sont de difficults essentiellement quivalentes :
factoriser n ;
calculer (n) ;
Si on connat la factorisation n = pq, on peut calculer aussitt (n) = (p1)(q1).
Rciproquement, supposons connu (n), et tentons de dterminer les entiers p et q.
Considrons le polynme P = X 2 (n + 1 (n))X + n Z[X]. Les coefficients
de P sont parfaitement connus. On observe que lon a lgalit P = (X p)(X q).
Bref, dterminer p et q se ramne la dtermination des racines de P . On pourrait

64

CHAPITRE 8. FACTORISATION DENTIERS, CRYPTOSYSTME RSA

appliquer lalgorithme du cours de factorisation dans Z[X], mais il est beaucoup plus
simple ici dutiliser les formules de rsolution des quations du second degr...
Proposition 8.8. Soit n un entier de la forme pq avec p et q premiers distincts.
Si on sait casser les clefs (n, e) (cest--dire dterminer la clef prive connaissant
la clef publique), on peut aussi factoriser n. Plus prcisment, admettons que lon
dispose dun programme C(e) qui dtermine si e est premier avec (n) et renvoie d
compris entre 1 et n tel que de 1 mod (n) si e est premier avec (n), alors pour
tout , en faisant au plus O(log1+
n ) appels C(), on peut dterminer (n), p et q.
On utilise le thorme des nombres premiers, que lon admet :
Thorme 8.9. Pour x R
+ , on note (x) le nombre de nombres premiers x
et pour tout n N , on note pn le n-ime nombre premier. Alors, (x) lnxx
x+

et pn

n+

n ln n.

Dmontrons la proposition 8.8. Commenons par observer que si lon a un candidat

pour (n), on peut vrifier rapidement que le rsultat est juste (cf. dmonstration de
la proposition 8.7). Supposons que lon ait dtermin un entier e 1 premier avec
(n) et tel que e O(log1+
n ). Si d = C(e), on a alors (n)|de 1, cest--dire quil
n
existe k 1 tel que de 1 = k(n). Comme 1 d n, do k e (n)
. Pour des
n
raisons videntes, (n) 3, do k 3e. On peut alors tester les nombres 1 l 3e,
gal (n) (1) .
jusqu trouver un diviseur de de 1, et un quotient de1
l
Lalgorithme est le suivant : on applique C(e), avec e = 2, 3, 4, . . . jusqu trouver
un e premier avec (n) auquel on applique ce qui prcde. Il faut cependant montrer
que le e trouv est O(log1+
n ) pour tout > 0. Il est vident que le plus petit e trouv
est un nombre premier et que cest le plus petit nombre premier ne divisant pas (n).
Le nombre k de nombres premiers divisant (n) est videmment log2 (n) log2 n.
Parmi les nombres premiers p1 , . . . , pk+1 , au moins un ne divise (n), ainsi le nombre
e trouv est tel que e pk+1 . Daprs le thorme des nombres premiers, e est un
O(log1+
n ).
Remarque 8.10. Ainsi, si on sait casser des clefs RSA, on sait aussi factoriser
des produits de deux nombres premiers. Cela ne signifie pas que dcoder des messages
chiffrs avec RSA implique de savoir factoriser ces entiers : on peut imaginer pouvoir
dcoder des messages sans dterminer la clef prive...
8.2.3. Signature. La cryptographie clef publique permet Alice non seulement de recevoir des messages cods, mais aussi de signer des documents.
Si x X est le document quAlice veut signer, elle peut calculer = SA (x). Le
document sign est le couple (x, ).
Tout personne (en particulier Bob) ayant sa disposition la clef publique PA dAlice
peut vrifier la signature en vrifiant lgalit x = PA (). Une telle galit (sauf
1. Si les nombres premiers p et q ont t choisis grands (tous les deux de lordre de
est trs proche de 1 ; on a alors intrt prendre pour l un entier approchant

(n)
n

n), le quotient

de1
.
n

8.2. CRYPTOGRAPHIE CLEF PUBLIQUE

65

pour des x et triviaux) ne pouvant en principe tre fabrique que par quelquun
disposant de la clef secrte SA , une telle signature authentifie lmetteur et le contenu
du message.

CHAPITRE 9
TRANSFORME DE FOURIER DISCRTE

Le but de ce chapitre est dexpliquer comment calculer efficacement le produit de

deux polynmes ou de deux entiers.

9.1. Racines de lunit

Dfinition 9.1. Soit n 1. Soit A un anneau dans lequel n est inversible. Soit
A. On dit que est une racine primitive n-ime de lunit si n = 1 et que pour
tout 1 i n 1, 1 i soit un lment inversible de A.
Pourvu que A ne soit pas lanneau nul, si est une racine primitive n-ime de lunit
dans A, alors le sous-groupe de A engendr par est dordre n ; la rciproque est
fausse en gnral, mais vraie si A est un corps.
Si est une racine primitive n-ime de lunit, alors i j est inversible si i 6 j
mod n.
Proposition 9.2. Soit A un anneau. Soit n 2. Soit une racine primitive
n-ime de lunit.
n

(i) Pour tout diviseur m de n, m est une racine primitive m-ime de lunit dans
A.
Pn1
(ii) Pour j 6 0 mod n, i=0 j = 0.
La proprit (i) est triviale. La proprit (ii) rsulte de la relation
(1 j )

n1
X

j = 1 nj = 0 ,

i=0
j

et du fait que 1 soit inversible.

2i

Remarque 9.3. Si A = C, = e n est une racine primitive n-ime de lunit,

de mme que 1 = ; plus gnralement, les racines primitives n-imes sont les i
avec i Z/nZ . Si A = Fq est un corps fini q lments (et que la caractristique

68

CHAPITRE 9. TRANSFORME DE FOURIER DISCRTE

de Fq ne divise pas n), alors A admet une racine primitive n-ime de lunit si et
seulement si n divise q 1.
Proposition 9.4. Soit A un anneau dans lequel 2 est inversible. Soit k 0. On
pose n = 2k+1 . Soit A. Alors, est une racine primitive n-ime de lunit si et
n
seulement si 2 = 1.
Montrons le rsultat pour k = 0. Soit A une racine primitive deuxime de
lunit. On a 2 = 1 et 1 inversible. La relation 2 = 1 se traduisant par (1 +
)(1 ) = 0, linversibilit de 1 conduit = 1. Rciproquement, 1 est bien
une racine primitive deuxime de lunit puisque lon a suppos 2 inversible.
Soit k 0. Si est une racine primitive 2k+1 -ime de lunit, daprs la proposik
tion 9.2, 2 est une racine deuxime de lunit. Daprs le cas prcdent, on a bien
k
2 = 1. Montrons la rciproque par rcurrence sur k. Le cas k = 0 a dj t trait.
k
k1
Supposons k 1 et 2 = 1. Posons 0 = 2 . On a 02
= 1. Par hypothse
de rcurrence, 0 est une racine primitive 2k -ime de lunit. Posons m = 2k . Le fait
que 0 soit une racine primitive m-ime de lunit signifie que 1 0i est inversible
pour 1 i m 1. Observons que 1 0i = (1 i )(1 + i ) = (1 i )(1 m+i ).
Ainsi, 1 i et 1 m+i sont inversibles pour 1 i m 1. Comme 1 m = 2 est
inversible, on obtient bien ainsi que pour tout 1 j 2m 1, 1 j est inversible,
cest--dire que est une racine primitive 2k+1 -ime de lunit.
Remarque 9.5. Soit A un anneau dans lequel 2 est inversible. Si n = 2k+1 avec
n
k 0, alors la classe de X dans lanneau quotient A[X]/(X 2 + 1) est une racine
primitive n-ime de lunit.

9.2. Transforme de Fourier discrte

On fixe un entier n 1, une racine primitive n-ime de lunit dans un anneau
A.
Dfinition 9.6. La transforme de Fourier discrte est lapplication A-linaire
TFD : A[X]<n An qui un polynme P de degr au plus n 1 associe le n-uplet
(P (1), P (), . . . , P ( n1 )).
Remarque 9.7. Les morphismes valuations en 1, , . . . , n1 sont dfinis sur
tout A[X]. Lidal engendr par X n 1 est bien sr dans le noyau de ces morphismes
dvaluations. Comme on a un isomorphisme canonique A[X]<n ' A[X]/(X n 1),
on peut considrer la transforme de Fourier discrte comme un morphisme
TFD : A[X]/(X n 1) An .
Thorme 9.8. On identifie canoniquement A[X]<n An faisant correspondre
(a0 , . . . , an1 ) a0 + a1 X + + an1 X n1 . On peut donc considrer les transforme
de Fourier discrte TFD et TFD1 des endomorphismes de An . On a alors,
TFD1 TFD = n idAn , autrement dit la transforme de Fourier discrte TFD
1
est un isomorphisme et son inverse TFD1
est n TFD 1 .

9.3. TRANSFORME DE FOURIER RAPIDE (FFT)

69

Notons V (resp. V 1 ) la matrice de TFD (resp. TFD 1 ) dans les bases canoniques. On a

1
1
1
...
1

2
...
n1

2
4
2(n1)

...

V =
.

..
..
..

1
.
.
...
.
1 n1 2(n1) . . . (n1)(n1)
Le terme gnral est ij pour 0 i, j n 1.
Il vient aussitt que V1 V = (i,j )0i,jn1 avec
i,j =

n1
X

ki kj .

k=0

Si i = j, on a videmment i,j = n. Si i 6= j, on a i,j = 0 daprs la proposition 9.2.

Corollaire 9.9. Si P et Q sont des polynmes coefficients dans A, alors
TFD (P Q) = TFD (P ) TFD (Q) ,
o lon a not le produit terme terme dans An . Si le degr de P Q est strictement
infrieur n, on a
1
TFD1 (TFD (P ) TFD (Q)) ,
n
avec labus de notation signal plus haut.
PQ =

Multiplier terme terme des lments de An ncessite uniquement n multiplications dans An . Ainsi, si on arrive calculer des transformes de Fourier discrte plus
efficacement quen O(n2 ) oprations, on obtiendra un algorithme de multiplication de
polynmes plus efficace que lalgorithme naf.

9.3. Transforme de Fourier rapide (FFT)

On prsente ici un algorithme permettant de calculer efficacement la transforme
discrte dans le cas o n est une puissance de deux.
On suppose que n = 2k . Notons une racine n-ime primitive de lunit. Pour
n
tout diviseur d de n, on note d = d : cest une racine primitive d-ime de lunit. Si
k = 0, il ny a essentiellement rien faire. Pour expliquer le principe de lalgorithme,
on suppose k 1, de sorte que lon peut crire n = 2m. On va montrer comment
calculer TFDn en combinant le rsultat de deux appels TFDm .
Pn1
Pm1
i
j
Soit P A[X]<n , P =
et Q1 =
j=0 a2j X
i=0 ai X . On pose Q0 =
Pm1
j
2
2
j=0 a2j+1 X . On a la relation P (X) = Q0 (X ) + XQ1 (X ). Ainsi, pour tout
0 i n 1, on a :
i
i
P (ni ) = Q0 (m
) + ni Q1 (m
).

70

CHAPITRE 9. TRANSFORME DE FOURIER DISCRTE

En utilisant le fait que nm = 1, on peut crire deux relations pour tout 0 i

m1 :
i
i
P (ni ) = Q0 (m
) + ni Q1 (m
)

i
i
P (nm+i ) = Q0 (m
) ni Q1 (m
).

i
i
Calculer les valeurs Q0 (m
) et Q1 (m
) pour 0 i m 1 revient calculer
TFDm (Q0 ) et TFDm (Q1 ). Une fois ce calcul fait, on peut utiliser les relations cidessus pour obtenir TFD (P ).
Une manire efficace de procder cette combination des deux rsultats de TFDm
consiste stocker dans deux tableaux t et t0 de taille m (index par les entiers compris
entre 0 et m1) les rsultats respectifs de TFDm (Q0 ) et TFDm (Q1 ) et de remplir de
la manire suivante un nouveau tableau r de taille n contenant le rsultat TFD (P ).
On initialise une variable x 1. Pour i allant de 0 jusqu m 1, on calcule u := x t0i ,
on fait ri := ti + u et rm+i := ti u et on fait x := x.
On peut appliquer lalgorithme ci-dessus rcursivement. Notons Ck le cot en
nombres doprations (addition, multiplication) dans A de lalgorithme de transforme de Fourier rapide pour des polynmes de degr < 2k . On a manifestement une
relation de rcurrence :
Ck = 2Ck1 + O(2k ) .

Il en rsulte que Ck = O(k2k ), autrement dit le cot est en O(n log2 n).

9.4. Multiplication rapide

Daprs le corollaire 9.9, on peut utiliser la transforme de Fourier discrte pour
calculer un produit de polynmes de degr n coefficients dans un anneau A en
n log2 n oprations dans cet anneau, pourvu que lon dispose de racines de lunits.
Plus prcisment, on a :
Proposition 9.10. Soit A un anneau muni dune racine n-ime de lunit , avec
n une puissance de deux. On peut calculer une multiplication dans A[X]/(X n 1) en
utilisant n multiplications dans A et O(n log2 n) additions dans A ou multiplications
dans A par une puissance de .
Corollaire 9.11. Soit A un anneau muni dune racine primitive 2n-ime de
lunit , avec n une puissance de deux. On peut calculer une multiplication dans
A[U ]/(U n + 1) en utilisant n multiplications dans A et O(n log2 n) additions dans A
ou multiplications dans A par une puissance de .
Soit une racine primitive 2n-ime de lunit. 2 est une racine primitive n-ime
de lunit et on a n = 1. Daprs la proposition, on sait calculer le produit dans
A[X]/(X n 1) en O(n log2 n) oprations daddition ou de multiplication par une
puissance de et en n multiplications dans A. Par ailleurs, on a un isomorphisme de

A-algbres A[X]/(X n 1) A[U ]/(U n + 1) envoyant X sur U et lisomorphisme

inverse U sur 1 X. Pour multiplier les polynmes en U modulo U n + 1, on passer
la reprsentation comme polynme en X en substituant U := 1 X, multiplier ces

9.4. MULTIPLICATION RAPIDE

71

polynmes en X, puis revenir la reprsentation comme polynme en U en substituant X := U . Le surcot par rapport lalgorithme prcdent nest quun O(n) de
multiplications par des puissances de .
Thorme 9.12. Soit A un anneau dans lequel 2 est inversible. On peut calculer
des produits dans A[X]/(X n + 1) avec n = 2k en O(n log2 n log2 log2 n) oprations
dans A.
k
k
Si k 2, on utilise un algorithme trivial. Sinon, on pose m = 2b 2 c , t = 2d 2 e
(n = mt). On se donne f et g deux lments de A[X]<n . On peut trouver duniques
lments f 0 , g 0 des A[X, Y ] tels que f 0 (X, X m ) = f , g 0 (X, X m ) = g et que f 0 et g 0
soient de degr < m par rapport X. On considre les images f ? et g ? de f 0 et g 0
dans lanneau quotient B[Y ]/(Y t + 1) avec B = A[X]/(X 2m + 1).
On applique lalgorithme du corollaire 9.11 pour dterminer le produit h? = f ? g ?
B[Y ]/(Y t + 1), les oprations de multiplications dans B tant ralises en appliquant
rcursivement lalgorithme que lon dcrit ici. Il faut prciser la racine 2t-ime primitive de lunit de B que lon utilise : si k est pair, m = t, la classe de X 2 est

t
une racine primitive 2t-ime de lunit dans B (car X 2 = X 2m = 1 dans B),
si k est impair, t = 2m, la classe de X est une racine primitive 2t-ime de lunit
dans B (car X t = X 2m = 1 dans B). On connat alors le produit h? de f ? et g ?
dans A[X]/(X 2m + 1)[Y ]/(Y t + 1). Notons h0 lunique lment de A[X][Y ]/(Y t + 1)
de degr < 2m par rapport X relevant h? . Le produit f g cherch est le reste de la
division euclidienne de h0 (X, X m ) par X n + 1.
En effet, comme les images de f 0 et g 0 dans A[X, Y ]/(Y t + 1) sont de degrs < m
par rapport X, limage de f 0 g 0 dans A[X, Y ]/(Y t + 1) est de degr < 2m par
rapport X ; les images de h0 et f 0 g 0 dans A[X, Y ]/(Y t + 1) concident, puisquils
concident modulo X 2m +1. Au lieu de rduire modulo X 2m +1, rduisons maintenant
par rapport lidal engendr par Y X m . Comme on a un isomorphisme vident
danneaux A[X]/(X n +1) ' A[X, Y ]/(Y t +1, Y X m ), on obtient une certaine galit
dans A[X]/(X n + 1), prcisment entre h0 (X, X m ) et f 0 (X, X m )g 0 (X, X m ) = f g.
tudions le cot de cet algorithme. Notons Ck le cot de la multiplication dans
k
A[X]/(X 2 + 1) en oprations arithmtiques (addition ou multiplication) dans A.
Faisons plusieurs observations :
Le calcul de f 0 , g 0 puis f ? , g ? partir de f et g et celui de h0 en fonction de h?
se fait videmment en O(n) oprations sur les lments de A.
Le calcul de f g partir de h0 se fait aussi en O(n) oprations sur les lments de
n
A. Il sagit en effet de calculer le reste de la division euclidienne
P2n1 pari X + 1 dun
0
polynme de degr < 2n coefficients dans A : si h = i=0 ai X , le reste est
Pn1
i
i=0 (ai an+i )X .
Lestimation qui reste faire est celle du cot de la multiplication de f ? et
de g ? dans B[Y ]/(Y t + 1). On utilise pour cela le corollaire 9.11 : on utilise t
multiplications dans B et O(t log2 t) additions dans B ou multiplications par des
puissances de .
Une addition dans B utilise 2m additions dans A. Une multiplication dans B par
une puissance de se fait en O(m) oprations dans A. Le cot des O(t log2 t)

72

CHAPITRE 9. TRANSFORME DE FOURIER DISCRTE

oprations de ces deux types utilises ci-dessus est donc un O(mt log2 t) = O(2k k)
oprations dans A.
On obtient finalement une relation de rcurrence :
k
Ck 2d 2 e Cb k c+1 + O(2k k) .
2

Notons Sk =

Ck
.
2k (k2)

On obtient :

k
k
2k (k 2)Sk 2d 2 e 2b 2 c+1


k
1 Sb k c+1 + O(2k k) .
2
2

Divisons par 2k (k 2) (on suppose k 3) :

Sk Sb k c+1 + O(1) .
2
On en dduit que Sk = O(log2 k), et donc Ck = O(2k k log2 k). Comme n = 2k , on a
bien un cot en O(n log2 n log2 log2 n) oprations dans A.
Thorme 9.13 (Schnhage-Strassen, 1971). On peut multiplier des entiers
n bits en O(n log2 n log2 log2 n) oprations lmentaires sur les bits.
On va prsenter un autre algorithme utilisant aussi la FFT. Il ne permet pas de
multiplier des entiers de taille arbitraire, mais possde un domaine de validit suffisant
pour les multiplications susceptibles dtre ralises compte tenu des capacits de stockage actuelles. Il prsente aussi lavantage dutiliser une reprsentation des nombres
entiers par blocs de 64 bits, qui est est la taille des registres sur certains processeurs
utiliss couramment de nos jours.
Soit s 61 un entier. On va dcrire un algorithme pour multiplier des entiers
s
naturels a et b tels que ab < 2642 . On prcalcule une fois pour toutes trois nombres
premiers impairs p1 , p2 , p3 distincts et compris entre 263 et 264 et des racines primitives
2s -imes i dans Fpi (lexistence de ces racines primitives revient demander que les
pi soient congrus 1 modulo 2s ).
On se donne deux entiers naturels n et n0 , reprsents chacun sous une forme
+ 2264 a2 + 26 4a1 + a0 avec 0 ai < 264 1, autrement dit P (264 ) et P 0 (264 ) o P
et P 0 sont des polynmes coefficients entiers compris entre 0 et 264 1. On suppose
que la somme des degrs de P et P 0 est < 2s (et on a intrt choisir s le plus petit
possible).
Pour i {1, 2, 3}, on calcule limage du produit P P 0 dans Fpi en utilisant lalgorithme de la proposition 9.10. En utilisant le lemme chinois (on a intrt prcalculer
aussi les coefficients appropris des relations de Bzout), on dtermine lunique polynme Q Z[X] coefficients compris entre 0 et p1 p2 p3 1 tel que Q P P 0
mod p1 p2 p3 .
On a alors Q = P P 0 . En effet, les coefficients de P P 0 sont des entiers naturels
2s 2264 261+264 = 2363 < p1 p2 p3 .
Le rsultat nn0 est Q(264 ), dont on peut dterminer rapidement la suite des blocs
de 64 bits partir des coefficients de Q.

9.5. UN ALGORITHME DE FACTORISATION DENTIERS (POLLARD, STRASSEN)

73

9.5. Un algorithme de factorisation dentiers (Pollard, Strassen)

9.5.1. Principe. Soit N 3 un entier (impair). Soit b un entier naturel. Lalgorithme suivant dtermine
l m le plus petit diviseur premier de N infrieur b sil en existe
N , on pourra donc dterminer le plus petit diviseur premier de
(en prenant b =
N ).
l m
Calculer c :=
b .
Qc
Dterminer f = j=1 (X + j) Z/N Z[X].
Calculer f (ic) Z/N Z pour 0 i c 1. On note gi un reprsentant de f (ic)
tel que 0 gi N 1.
On dtermine le plus petit entier k tel que gi N 6= 1. (Sil nen existe pas, on
renvoie FAIL.)
Lentier p renvoyer est tel que kc + 1 p (k + 1)c. On renvoie le plus petit
entier p de cet intervalle tel que p|N . (Remarque : Il se peut que lentier p rendu
soit un peu plus grand que b.)
Les quantits gi vrifient :
gi (ic + 1)(ic + 2) . . . (ic + c)

mod N .

Ainsi, gi N = 1 si et seulement si tous les entiers ic + 1, ic + 2, ..., ic + c sont premiers

N . Les intervalles dentiers ic + 1, . . . , icc correspondant aux indices 0 i c 1
partitionnent lensemble des entiers compris entre 1 et c2 (c2 b). En dterminant le
plus petit i tel que gi ne soit pas premier avec N , on obtient un intervalle dentiers
dans lequel se trouve le plus petit entier p qui nest pas premier avec N . Le plus petit
de ces entiers est forcment premier, donc on peut aussi bien tester que p divise N
que vrifier que p N 6= 1.
Cet algorithme nest vraiment intressant que si on utilise des algorithmes efficaces
pour le calcul du polynme f et lvaluation de f en les entiers considrs modulo N .
En effet, si on considre comme lmentaires les oprations arithmtiques sur les
lments de Z/N Z, lalgorithme naf de calcul de f exige O(c2 ) = O(b) oprations et
de mme le calcul des gi demande aussi O(b) oprations. Bref, la complexit est la
mme que celle de lalgorithme naf qui consiste parcourir les entiers de 2 jusque
vers N en sarrtant ds que lon rencontre un diviseur de N .
9.5.2. Produit multiple de polynmes. Pour calculer f , et plus gnralement pour calculer un produit de polynmes Pi , 1 i 6= n, on nutilisera donc pas
lalgorithme naf qui consisterait calculer successivement P1 , P1 P2 , P1 P2 P3 , etc. On
utilise plutt lalgorithme suivant :
Si n = 0, renvoyer 1 ; si n = 1, renvoyer P1 .
Qb n2 c
Qn
Calculer rcursivement A = i=1
Pi et B = i=b n c+1 Pi .
2
Appliquer lalgorithme du thorme 9.12 pour calculer le produit AB et renvoyer
le rsultat.
Notons M(d) un majorant du cot dun algorithme de multiplication des polynmes
de degrs d. On suppose que M(n)
est une fonction croissante (et on peut supposer
n
que cette dernire est un O(log n log log n)). Cette proprit implique que M(m+n)

74

CHAPITRE 9. TRANSFORME DE FOURIER DISCRTE

M(m) + M(n). En effet, on peut supposer m n m + n, do M(m)

M(n)

m
n
M(m+n)
m+n
m
m+n , dont on tire M(m + n)
n M(n) = M(n) + n M(n) M(n) + M(m).
Montrons par rcurrence sur r 0 que pour tout n tel que n 2rP
, le cot du
n
produit des n polynmes par lalgorithme ci-dessus est rM(d) o d = i=1 deg Pi .
Supposons le rsultat vrai pour r0 < r, montrons le pour r. Soit n 2r . Le calcul
de A et de B va consister en deux appels rcursifs une situation o la profondeur
du calcul r0 sera r0 r 1 et avec deux ensembles de polynmes sont les sommes
respectives des degrs d0 et d00 vrifient d0 + d00 = d. Le calcul de A et de B exige donc
(r 1)(M(d0 ) + M(d00 )) (r 1)M(d) oprations. Le calcul de AB connaissant A
et B cote au plus M (d) oprations supplmentaires, do le rsultat.
Bref, on peut calculer un produit de n polynmes
P Pi en O(log2 nd log2 d log2 log2 d)
oprations arithmtiques dans lanneau, o d = i Pi .
l m
N , on peut donc
Dans lalgorithme dcrit dans la sous-section 9.5.1, pour b =
1

calculer f en O(N 4 log22 N log2 log2 N ) oprations dans Z/N Z. Le plus important
1
1
noter est la puissance de N qui intervient : N 4 plutt que N 2 , avec lalgorithme naf.
9.5.3. valuations multiples dun polynme. On se donne un polynme f
de degr n = 2k , des scalaire u0 , u1 , . . . , un1 et on veut calculer f (u0 ), . . . , f (un1 ).
OnQpeut garder en mmoire les rsultats intermdiaires du calcul du pron1
duit
i=0 (X ui ) par lalgorithme de la sous-section 9.5.2. Notons Mi,j =
Q
ki
. (On commence par initialiser les
0k<2i (X uj2i +k ) pour 0 j < 2
M0,j , ensuite les Mi+1, sobtiennent chacun en faisant le produit de deux Mi, :
Mi+1,j = Mi,2j Mi,2j+1 .)
Les Mi,j tant calculs, on va ensuite procder au calcul des restes Ri,j de la
division euclidienne de f par tous ces Mi,j , de faon ce que pour i = k, on obtienne
f (uj ), qui est gal Rk,j .
On procde ainsi. On initialise Rk,0 la valeur du reste de la division euclidienne
de f par Mk,0 . Ensuite, pour i allant de k 1 0, et pour j allant de 0 2ki 1,
on calcule le reste Ri,j de la division euclidienne de Ri+1,b j c par Mi,j .
2
Par rcurrence descendante sur i, on montre que Ri,j est congru f modulo Mi,j .
En effet, par hypothse de rcurrence, Ri+1,b j c f mod Mi+1,b j c . Comme Mi,j
2
2
divise Mi+1,b j c et que Ri,j Ri+1,b j c mod Mi,j , il vient Ri,j f mod Mi,j .
2

On sait que le cot du calcul des Mi,j est intressant, mais pour que les f (ui ) soient
calculs efficacement, encore faut-il que lalgorithme de division euclidienne utilis ici
soit rapide. Nous allons voir quune division euclidienne entre polynmes de degrs
d peut se faire en O(M(d)) oprations, ce qui permet dobtenir un rsultat similaire
celui obtenu dans la sous-section prcdente.
9.5.4. Division euclidienne.
9.5.4.1. Inversion modulo X k . Soit k un corps. Nous allons dcrire un algorithme
permettant, tant donn un polynme P k[X]<m de terme constant non nul, de
dterminer Q k[X]<m tel que P Q 1 mod X m .

75

9.5. UN ALGORITHME DE FACTORISATION DENTIERS (POLLARD, STRASSEN)

On raisonne dans lanneau A = k[X]/(X m ). On peut rapprocher ceci de la mthode

1
P .
de Newton. Considrons la fonction f qui Q inversible dans A associe f (Q) = Q
On cherche Q tel que f (Q) = 0. Si on avait affaire une fonction dune variable relle
x, on aurait f (x) = x1 y (o y jouerait le rle de P ). f 0 (x) = 1
x2 . La mthode de
n)
Newton consisterait alors tudier une suite xn dfinie par xn+1 = xn ff0(x
(xn ) =
2xn yx2n . La dfinition de cette suite ne fait plus intervenir de division ! Il nest ds
lors plus draisonnable de dfinir une suite Qn k[X] par Q0 = 1, Qn+1 = 2Qn P Q2n
n+1
mod X 2 .
n

Lemme 9.14. Si P k[X] est de terme constant 1, alors P Qn 1 mod X 2 .

Lhypothse sur le terme constant 1 assure que P Q0 1 mod X. Montrons
lnonc gnral par rcurrence sur n. On a 1 P Qn+1 1 2P Qn + P 2 Q2n
n+1
(1 P Qn )2 0 mod X 2 .
Cet algorithme permet de calculer linverse dun lment dans k[X]/(X m ) avec
m = 2k (et donc pour tout valeur de m, en allant jusqu la premire puissance de 2
suprieure m et en tronquant le polynme obtenu).
Proposition 9.15. Le calcul dun inverse dans k[X]/(X n ) peut se faire en
O(M(n)).
Quitte utiliser une proprit de la fonction M non nonce encore, savoir
M(mn) m2 M(n), on peut supposer que n = 2k . Lalgorithme ci-dessus consiste
calculer Q0 , Q1 , . . . , Qk , le rsultat final tant Qk . Le cot de lalgorithme se rpartit
dune part en des additions de polynmes de degrs 2i pour i allant de 1 k, ce
qui conduit un cot en O(2k ), certainement infrieur M(2k ), et dautre part en
des multiplications. Pour le calcul de Qi en fonction de Qi1 , on a besoin de deux
multiplications entre polynmes de degrs < 2i , cest--dire 2M(2i ). On utilise la
1
relation M(2i ) 2ki
M(2k ) pour obtenir que le cot de toutes ces multiplications
Pk
1
k
4M(2k ), do le rsultat.
est infrieur 2M(2 ) i=1 2ki
9.5.4.2. Division euclidienne rapide.
1
Dfinition 9.16. Soit P k[X]d . On note revd P = X d P ( X
).

On se donne deux polynmes non nuls A, B k[X], a = deg A, b = deg B. On

veut calculer le reste et le quotient de la division euclidienne de A par B. On procde
ainsi.
Si a < b, le quotient Q est 0 et le reste R est A.
Sinon, on note m = a b. On calcule linverse I k[X]m de revb B modulo
X m+1 grce lalgorithme ci-dessus.
On calcule le produit reva A I et on note Q? son reste modulo X m+1 .
On note Q = revm Q? et on calcule R = A BQ.
Montrons que le rsultat rendu est correct. Par dfinition de I, on a I revb B 1
mod X m+1 . En multipliant par reva A, il vient :
Q? revb B reva A mod X m+1 .

76

CHAPITRE 9. TRANSFORME DE FOURIER DISCRTE

Il existe donc W k[X] tel que

Q? revb B = reva A + W X m+1 .
Faisons le changement de variables X := 1/X et multiplions par X a , on obtient :
X m Q? (1/X)B(X) = A(X) + W (1/X)X b1 .
Par construction, Q? est de degr m, donc cela a un sens de considrer le polynme
Q := revm Q? . On a ainsi une galit dans k(X) : QBA = W (1/X)X b1 . Le membre
de gauche tant dans k[X], le membre de droite y est aussi. La quantit W (1/X)X b1
est donc manifestement un polynme de degr < b, qui est donc loppos du reste de
la division euclidienne de A par B, ce qui montre que Q est bien le quotient cherch,
le reste est aussi R := A BQ.
Daprs les rsultats prcdents, on peut majorer le cot de cet algorithme par un
O(M(a))

CHAPITRE 10
MTHODES DINTERPOLATION

10.1. Interpolation de Lagrange

Linterpolation de Lagrange consiste, tant donns x0 , . . . , xn des nombres rels
distincts et des valeurs a0 , . . . , an trouver lunique polynme P de degr n tel que
P (xi ) = ai .
10.1.1. Vandermonde.
Dfinition 10.1. Soit A un anneau (commutatif). Soit x = (x1 , . . . , xn ) An .
Notons evx lapplication A-linaire A[X]<n An qui P associe le n-uplet
(P (a1 ), . . . , P (an )). Le dterminant de Vandermonde V (x1 , . . . , xn ) est le dterminant de evx par rapport la base canonique de An et la base canonique
(1, X, . . . , X n1 ) de A[X]<n
Proposition 10.2. Le dterminant V (x1 , . . . , xn )
trice suivante :

1 x1 x21 . . . xn1
1

..
..
..
1 .
. ...
.
1

xn

x2n

...

est le dterminant de la ma

xn1
n

En effet, cette matrice est la transpose de la matrice de evx dans les bases considres.
Proposition 10.3. On a le formulaire suivant :
V (0, x2 , . . . , xn )

x2 . . . xn V (x2 , . . . , xn ) ;

V (x1 + a, x2 + a, . . . , xn + a)

V (x1 , . . . , xn ) .

La premire relation dcoule facilement du dveloppement de V (0, x1 , . . . , xn ) par

rapport la premire ligne. Montrons la deuxime. Notons x + a le n-uplet x1 +
a, . . . , xn + a. On a la relation suivante entre homomorphismes : evx a = evx+a o
a : A[X]<n A[X]N est P 7 P (X + a). Pour obtenir V (x) = V (x + a), il suffit

78

CHAPITRE 10. MTHODES DINTERPOLATION

de montrer que le dterminant de a dans la base canonique est 1, ce qui rsulte du

fait que sa matrice soit triangulaire suprieure avec des 1 sur la diagonale.
Corollaire 10.4.
Y

V (x1 , . . . , xn ) =

(xj xi ) .

1i<jn

On procde par rcurrence sur n. Pour n = 0, cest tautologique. On suppose la

relation connue pour les (n 1)-uplets. On utilise le formulaire :
V (x1 , . . . , xn )

V (0, x2 x1 , x3 x1 , . . . , xn x1 )

(x2 x1 )(x3 x1 ) . . . (xn x1 )V (x2 x1 , . . . , xn x1 )

(x2 x1 )(x3 x1 ) . . . (xn x1 )V (x2 , . . . , xn )

Y
= (x2 x1 )(x3 x1 ) . . . (xn x1 )
(xj xi )

2i<jn

(xj xi ) .

1i<jn

10.1.2. Interpolation. Daprs le corollaire 10.4, si x0 , . . . , xn sont des rels distincts, lapplication linaire R[X]n Rn+1 qui P associe (P (x0 ), . . . , P (xn )) est
un isomorphisme (on peut aussi montrer directement que le noyau de cette application
est nul). tant donn x0 , . . . , xn des nombres rels distincts et des valeurs a0 , . . . , an ,
il existe bien un unique unique polynme P de degr n tel que P (xi ) = ai .
Proposition 10.5. Avec les notations ci-dessus, on a lgalit :
n
X
ai Li .
P =
i=0

o Li =

Q
(Xxj )
Q j6=i
.
j6=i (xi xj )

Les polynmes L0 , . . . , Ln sont les interpolants de Lagrange

associs (x0 , . . . , xn ).
Les polynmes Li vrifient videmment Li (xj ) = ij . Le rsultat en dcoule aussitt.
Proposition 10.6. tant donn des rels distincts x0 , . . . , xn et des valeurs
a0 , . . . , an , le calcul des coefficients du polynme interpolateur de Lagrange correspondant peut se faire en O(n2 ) oprations lmentaires sur les coefficients.
2
Il suffit de montrer que lon peut calculer les interpolants
PnL0 , . . . , Ln en O(n ) oprations lmentaires, le calcul de la combinaison linaire i=0 ai Li se faisant ensuite
en O(n2 ) oprations.
On commence par calculer itrativement le produit Q = (X x0 ) . . . (X xn ) de
degr Q
n + 1 ; ceci se fait en O(n2 ) oprations. Pour chaque 0 i n, le polynme
Qi = j6=i (X xj ) est le quotient (juste) de la division euclidienne de Q par X xi .
Le polynme X xi tant de degr fix 1, chacune de ces divisions euclidiennes peut
tre faite en O(n) oprations ; comme il y en a n, on obtient un cot en O(n2 ). Pour

10.1. INTERPOLATION DE LAGRANGE

79

Q
chaque 0 i n, on calcule j6=i (xj xi ) (cot : O(n) oprations) et on multiplie
les coefficients de Qi par ce nombre pour obtenir Li , ce qui demande encore O(n)
oprations. En prenant en compte les n + 1 polynmes obtenir, on obtient encore
une contribution en O(n2 ), do le rsultat.
10.1.3. Majoration de lerreur.
Proposition 10.7. Soit f : I R une fonction de classe C n+1 sur un intervalle ouvert I. Soit (x0 , . . . , xn ) un (n + 1)-uplet dlments distincts de I. Soit P
le polynme de degr n interpolant f en les xi . Alors, pour tout x I, on a la
majoration :
!

n
f (n+1)
Y

.
|f (x) P (x)|
|x xi |
(n
+
1)!
i=0
La drive (n + 1)-ime de P tant nulle, quitte remplacer f par f P , on peut
supposer que f (xi ) = 0 pour 0 i n, cest--dire que P = 0. Fixons x I. Pour
montrer lingalit voulue, on peut supposer que x est diffrent des xi . Dfinissons
Qn
une fonction g par g(t) = f (t) i=0 (t xi ) o = Qn f (x)
. La fonction g est
i=0 (xxi )
de classe C n+1 et sannule en les n + 2 points distincts x, x0 , . . . , xn . En utilisant le
thorme de Rolle g et ses drives successives, on obtient que g (n+1) sannule un
point I.
(n+1)
()
On a g (n+1) (t) = f (n+1) (t) (n + 1)!, do = Qn f (x)
= g (n+1)!
, ce qui
i=0 (xxi )
permet de conclure.
10.1.4. Polynmes de Tchebychev.
Proposition 10.8. Pour tout n N, il existe un unique Tn R[X] tel que
cos nx = Tn (cos(x)) pour tout x R.
Lunicit est vidente, montrons lexistence de Tn par rcurrence sur n. On a videmment T0 = 1, T1 = X. Pour = 1, on a :
cos((n + 1)x + x) = cos(n + 1)x cos x sin(n + 1)x sin x .
En ajoutant membre membre les deux galits obtenues, on obtient :
cos(n + 2)x + cos nx = 2 cos x cos nx .
Par rcurrence sur n, on obtient aussitt que les Tn existent et satisfont la relation
de rcurrence Tn+2 + Tn = 2XTn+1 .
Proposition 10.9. Le polynme Tn est de degr n, ses zros sont les cos( (2k+1)
)
2n
pour 0 k n 1 et son coefficient dominant est 2n1 (sauf pour n = 0 o il vaut
1) ; ces proprits caractrisent Tn .
Le calcul du degr et du coefficient dominant rsulte aussitt de la relation de
rcurrence obtenue plus haut. Concernant les zros, on peut dterminer ceux appartenant [1, 1] en les mettant sous la forme x = cos avec 0 , la condition
est que n soit de la forme 2 + k avec k Z (et donc forcment 0 k n 1).

80

CHAPITRE 10. MTHODES DINTERPOLATION

Comme on dtermine ainsi n racines distinctes et que le polynme Tn est de degr n,

on les a toutes.
Lintrt des polynmes de Tchebychev pour le problme de linterpolation de Lagrange est que les zros x0 , . . . , xn de Tn+1 sont les valeurs pour lesquelles la majoration de lerreur de la proposition 10.7 est la meilleure (pourvu que lon travaille sur
lintervalle [1, 1], auquel on peut se ramener par un changement de variable affine).
Proposition 10.10. Soit n 0. Posons xi = cos( (2k+1)
2(n+1) ) pour 0 k n.
1
Alors, k(X x0 ) . . . (X xn )k = 2n (la norme kk est ici relative lintervalle
[1, 1]).
Pour tout polynme unitaire Q R[X] de degr n + 1, on a kQk 21n . Le cas
dgalit mis en vidence ci-dessus est le seul.
Posons P = (X x0 ) . . . (X xn ). Bien sr, R = T2n+1
n . Par construction,
k
|Tn+1 (x)| 1 pour 1 x 1 et les cas dgalits sont les yk = cos (n+1)
pour
k

0 k n + 1. On a donc bien kP k = 21n . Par ailleurs, on a P (yk ) = (1)

2n .
Supposons que kQk < 21n . Considrons D = P Q. Pour k pair, on a D(yk ) > 0
et pour k impair, on a D(yk ) < 0. Daprs le thorme des valeurs intermdiaires,
pour 0 k n, D sannule sur lintervalle ]yk+1 , yk [. Le polynme D a donc au
moins n + 1 zros ; comme P et Q sont unitaires de degr n + 1, D est de degr n,
do D = 0. Par consquent, Q = P , ce qui contredit lhypothse kQk < 21n . Plus
prcisment, si kQk 21n , on peut aussi conclure que D = 0 en utilisant le lemme
suivant :
Lemme 10.11. Soit P R[X]. On suppose que P 6= 0. Soit (x0 , . . . , xn ) un
n + 1-uplet de rels vrifiant x0 < x1 < < xn . On suppose que pour tout 0 i n,
(1)i P (xi ) 0. Alors, deg P n.
Une autre manire dnoncer que deg P n consiste dire que, si on prend en
compte les multiplicits, P a au moins n racines.
Procdons par rcurrence sur n. Pour n = 0, il ny a rien dire. Pour n = 1, cest
vident. Supposons le rsultant connu pour le n-uplet (x0 , . . . , xn1 ) et montrons quil
lest aussi pour (x0 , . . . , xn ).
Supposons dans un premier temps que P ait un zro dans lintervalle ]xn1 , xn ].
P
Posons Q = X
. Le polynme Q vrifie les hypothses du lemme relativement au
n-uplet (x0 , . . . , xn1 ), donc deg Q n 1, do deg P n.
Supposons maintenant que P nait pas de zro dans ]xn1 , xn ]. On a donc
(1)n P (xn ) > 0. On a aussi (1)n P (xn1 ) 0. Si on avait (1)n P (xn1 ) 0,
P aurait un zro dans ]xn1 , xn [, contradiction. Donc (1)n P (xn1 ) = 0, et
P
(1)n P (x) > 0 pour tout x ]xn1 , xn ]. Considrons Q = xn1
X . Pour 0 i n2,
i
0
on a bien sr (1) Q(xi ) 0. Par ailleurs, Q(xn1 ) = P (xn1 ). En calculant la
drive droite de P en xn1 , on obtient que (1)n1 Q(xn1 ) 0. Par hypothse
de rcurrence, deg Q n 1, do deg P n.

10.2. DIFFRENCES FINIES

81

10.2. Diffrences finies

10.2.1. Interpolation par diffrences finies.
Dfinition 10.12. Si f : R R est une fonction, on note f la fonction dfinie
par (f )(x) = f (x + 1) f (x).
Si f est la fonction polynmiale associe un polynme P , on note P le polynme
correspondant f .
Proposition 10.13. Soit P R[X]n . On a lgalit :
P = P (0)+X P (0)+

1
1
X(X 1)2 P (0)+ + X(X 1) . . . (X n+1)n P (0) .
2!
n!

La relation tablir tant linaire, il suffit de la tester sur une base convenable du
R-espace vectoriel R[X]n . Considrons les polynmes Pi = i!1 X(X 1) . . . (X i+1).
Comme ils sont chelonns en degrs, ces polynmes P0 , . . . , Pn forment une base de
R[X]n . Il suffit donc de vrifier la formule ci-dessus avec P = Pi .
On vrifie aussitt que pour tout i 1, Pi = Pi1 , et que P = 0. Par consquent, pour tout i 0, on a j Pi (0) = 0 pour 0 j i 1, i Pi (0) = 1 et
j Pi (0) = 0 pour j > i. Ceci permet de vrifier aussitt la formule pour P = Pi .
Remarque 10.14. Ainsi, pour retrouver un polynme P de degr n, il suffit
de connatre les valeurs i P (0) pour 0 i n. Par construction, ces valeurs ne
dpendent que de P (0), P (1), . . . , P (n). La formule ci-dessus peut-tre vu comme
une formule dinterpolation : le membre de droite lunique polynme de degr n
concidant avec P en 0, 1, . . . , n.
Proposition 10.15. Soit f : I R une fonction de classe C n+1 sur un intervalle
ouvert I contenant [0, n]. Alors, pour tout x I, on a la majoration :


n


X
i f (0)  |x(x 1) . . . (x n)|

(n+1)
x(x 1) . . . (x i + 1)
f (x)

f
.

i! 
(n + 1)!

i=0
Ceci rsulte de la proprit correspondant pour linterpolation de Lagrange.
10.2.2. Lien avec la formule de Taylor. On va voir que lon peut modifier
loprateur de diffrences finies de faon autoriser un pas autre que 1 et que la
formule ci-dessus se transforme en la formule de Taylor quand on fait tendre vers 0.
Dfinition 10.16. Soit f : R R une fonction. Pour tout > 0, notons f la
(x)
.
fonction dfinie par f (x) = f (x+)f

1
Notons Pi, le polynme Pi, = i! X(X )(X 2) . . . (X (i 1)).
Proposition 10.17. Soit P R[X]n . Pour tout > 0, on a lgalit :
P = P (0)+X (P )(0)+

1
1
X(X)2 P (0)+ + X(X) . . . (X(n1))n P (0) ,
2!
n!

82

CHAPITRE 10. MTHODES DINTERPOLATION

cest--dire que :
P =

n
X

k P (0)Pk, .

k=0

La formule est connue dans le cas = 1. On peut sy ramener en considrant le

polynme P (X).
Proposition 10.18. Pour tout k, la limite (dans R[X]k ) de Pk, quand tend
1
Xk.
vers 0+ est k!
Pour tout 0 k n, la limite de k P (0) quand tend vers 0+ est P (k) (0). Plus
gnralement, la famille de fonctions k P converge simplement vers P (k) quand
tend vers 0+ .
Le premier nonc est trivial. Pour le deuxime, considrons le lemme suivant :
Lemme 10.19. Soit A une Q-algbre. Soit  A. Soit n 0. Alors les polynmes
1
P0, , . . . , Pn, dfinis par Pk, = k!
X(X )(X (n 1)) forment une base du Amodule A[X]n .
La matrice de ces polynmes dans la base canonique est triangulaire suprieure
avec des 1 sur la diagonale. Son dterminant est donc inversible dans A.
Considrons le cas A = R[]. Soit P R[X]n . Considrons P comme un lment
de A[X] ' R[, X]. Daprs le lemme, il existe duniques polynmes D0 , . . . , Dn dans
R[] tels que
n
X
Dk Pk, .
P =
k=0

Si fait la substitution  := pour un > 0, on obtient

P =

n
X

Dk ()Pk, .

k=0

On a donc, Dk () = k P (0).
Par ailleurs, si on fait la substitution  := 0, comme il a t dit, Pk,0 = X k . Les
coefficient Dk (0) sont donc bien sr ceux qui interviennent dans la formule de Taylor :
1 (
Dk (0) = k!
P k)(0).
La relation nonce dans R[, X] plus haut fait intervenir des polynmes, que lon
peut donc considrer comme des fonctions continues en les deux variables relles. On
obtient donc :
lim k P (0) = P k (0) .

0+

(Cette conclusion se gnralise aussitt au cas o P serait remplac par une fonction
de classe C n+1 .)

10.3. INTERPOLATION DE HERMITE

83

10.3. Interpolation de Hermite

10.3.1. Principe. Soit k un corps. Soit x0 , . . . , xr des lments distincts de k.
On se donne des entiers naturels non nuls e0 , . . . , er . On pose n = e0 + + er .
Linterpolation de Hermite consiste dterminer lunique polynme de degr < n
admettant un dveloppement de Taylor fix lordre ei + 1 en xi .
Dire que deux polynmes P et Q ont le mme dveloppement de Taylor dordre
e + 1 en x revient dire que P Q mod (X x)e .
Proposition 10.20. On utilise les notations ci-dessus. Soit P0 , . . . , Pn k[X].
On suppose que Pi k[X]<ei . Il existe un unique polynme P k[X]<n tel que pour
tout i, on ait P Pi mod (X xi )ei .
Ceci rsulte aussitt du lemme chinois appliqu aux polynmes premiers entre eux
deux--deux (X xi )ei .
Remarque 10.21. De mme que pour linterpolation de Lagrange, on peut faire
une interpolation de Hermite en O(n2 ) oprations dans k.
10.3.2. Gnralisation de lalgorithme dEuclide tendu. On sait que lalgorithme dEuclide tendu permet, partant de deux polynmes non nuls P et Q
dans k[X] (k un corps), de dterminer U k[X]<deg Q et V k[X]<deg P tels que
U P + V Q = D o D est le pgcd de P et de Q. Si P et Q sont premiers entre eux, on
peut prendre D = 1. Dans ce cas, on observe que V Q est congru 1 modulo P et
0 modulo Q et que U P est congru 0 modulo P et 1 modulo Q. Le cot du calcul
de U et de V est en O(deg P deg Q) oprations lmentaires dans k.
On se propose de gnraliser ceci au cas o lon aurait P
1 , . . . , Pr (non constants)
P
Q
premiers entre eux deux--deux. Posons ei = deg Pi , n = i ei . Notons P = i Pi ,
Qi = P/Pi .
Proposition 10.22. Avec les notations ci-dessus, pour tout i, il existe un unique
Ui k[X]<di tels que Ui Qi soit congru 1 modulo Pi et 0 modulo Pj .
Ceci rsulte du lemme chinois appliqu aux polynmes premiers entre eux Pi et
Qi . Une autre manire de dire les choses est que Ui est un reprsentant de linverse
de Qi modulo Pi .
Connaissant les Ui et les Qi , on peut rsoudre facilement les congruences multiples :
Corollaire 10.23. Avec les notations ci-dessus, supposons donns de plus des
polynmes Ai k[X]
P <di . Lunique polynme A k[X]<n tel que A soit congru
Ai modulo Pi est i Ri Qi o Ri est le reste de la division euclidienne de Ai Ui par
Pi . Connaissant les Ui et les Qi , le calcul de A peut se faire en O(n2 ) oprations
lmentaires dans k.
On rappelle que le calcul du quotient et du reste dune division euclidienne dun
polynme P par un polynme non constant Q peut se faire O(deg P deg Q) oprations
lmentaires dans k. Le cot de la multiplication Ai Ui est O(d2i ). Celui de Ri en

84

CHAPITRE 10. MTHODES DINTERPOLATION

P
fonction de Ai Ui est aussi O(d2i ). Comme i d2i n2 . On peut calculer les Ri en
O(n2 ) oprations.
Le cot de la multiplication Ri Qi est O(deg Ri deg Qi ), donc un O(di n). Ces r
multiplications prennent donc O(n2 ) oprations. Chacun des polynmes Ri Qi est
de degr < n. Sommer ces r polynmes peut aussi se faire en O(n2 ) oprations
lmentaires dans k, ce qui permet de conclure.
Proposition 10.24. Le calcul des Ui et Qi en fonction des Pi peut se faire en
O(n2 ) oprations dans k. En particulier, la rsolution de congruences peut tre faite
en O(n2 ) oprations dans k.
Q
On calcule le produit P = i Pi . Notons un rel strictement positif tel que le
cot dun produit de polynmes de degrs p > 0 et q > 0 soit pq. Le cot du
calcul de P P
est donc [d1 dP
2 + (d1 + d2 )d3 + + (d1 + d2 + + dr1 )dr ]. On
reconnat 1i<jr di dj i,j di dj = n2 .
Le calcul de Qi = P/Pi se fait en O(di n) oprations. Les Qi peuvent donc tre calculs en O(n2 ) oprations. Il sagit ensuite dappliquer lalgorithme dEuclide tendu
aux polynmes Qi et Pi pour tout i. Chacun de ces calculs prend O(di (n di )) =
O(di n) oprations, do un cot total de O(n2 ) oprations.