232
7 La cryptographie ` a cl´ e publique
le reste de la division de aa
par n. C’est encore un nombre de E relativement premier
avec n. Notre op´ eration de groupe est a ∗ a
= a
: c’est la multiplication modulo n, et G
est ferm´ e sous cette op´ eration. Il est facile de v´ erifier qu’elle est associative et que 1 est
un ´ el´ ement neutre. Le fait que tout ´ el´ ement a un inverse est une cons´ equence imm´ ediate
du corollaire 7.6.
Le groupe G a moins de n−1 ´ el´ ements. Le sous-ensemble de G form´ e des ´ el´ ements qui
satisfont `
a la deuxi` eme moiti´ e de (7.4) est un sous-groupe H de G ; nous ne prouverons
pas cette affirmation. G et H sont des groupes finis. Par le th´ eor` eme de Lagrange, le
nombre d’´ el´ ements de H divise le nombre d’´ el´ ements de G. Deux cas sont possibles. Soit
H = G, auquel cas |H| = |G|. Sinon, |H| est un diviseur strict de |G|. En particulier,
|H| ≤
|G|
2 . On peut cependant montrer qu’il existe a ∈ G tel que J(a, n) n’est pas
congru `
a a
n−1
2
modulo n, ce qui exclut le cas |H| = |G|. Cette preuve est avanc´ ee et
nous ne la ferons pas ici.
Alors, |H| ≤
|G|
2 <
n−1
2 .
Th´ eor` eme 7.20 Si n est un nombre premier impair, alors tous les nombres a ∈ E =
{1, . . . , n − 1} r´ eussissent le test, c’est-` a-dire satisfont `
a (7.4).
Nous mettons en ´ evidence sous forme de r´ esultats distincts des parties de la preuve
qui nous seront utiles dans d’autres chapitres.
Lemme 7.21 1. Soient n un nombre premier, S = {0, 1, . . . , n − 1} et P (x) un polynˆ ome
P (x) = x
r + a r−1 x
r−1 + · · · + a 1 x + a 0
tel que a i ∈ S. Alors, il existe au plus r solutions x i ∈ S de la congruence
P (x) ≡ 0 (mod n).
2. Dans le cas particulier du polynˆ ome P d (x) = x
d
− 1 pour d | n − 1, la congruence
P d (x) ≡ 0 (mod n) a exactement d solutions distinctes dans E = S \ {0}.
Preuve 1. La preuve se fait par induction sur r. C’est vrai pour r = 1. Supposons
que ce soit vrai pour tout polynˆ ome de degr´ e r et montrons-le pour un polynˆ ome
P (x) de degr´ e r + 1. Supposons qu’il existe a 1 ∈ E tel que P (a 1 ) ≡ 0 (mod n).
Divisons le polynˆ ome P (x) par x − a 1 . Nous obtenons
P (x) = (x − a 1 )Q(x) + β,
o` u Q(x) est un polynˆ ome de degr´ e r ` a coefficients dans Z. Soit
Q(x) = x
r + b r−1 x
r−1 + · · · + b 1 x + b 0 ,
et soient b i ≡ c i (mod n) et β ≡ γ (mod n) pour c i , γ ∈ S. Posons
7 La cryptographie ` a cl´ e publique
le reste de la division de aa
par n. C’est encore un nombre de E relativement premier
avec n. Notre op´ eration de groupe est a ∗ a
= a
: c’est la multiplication modulo n, et G
est ferm´ e sous cette op´ eration. Il est facile de v´ erifier qu’elle est associative et que 1 est
un ´ el´ ement neutre. Le fait que tout ´ el´ ement a un inverse est une cons´ equence imm´ ediate
du corollaire 7.6.
Le groupe G a moins de n−1 ´ el´ ements. Le sous-ensemble de G form´ e des ´ el´ ements qui
satisfont `
a la deuxi` eme moiti´ e de (7.4) est un sous-groupe H de G ; nous ne prouverons
pas cette affirmation. G et H sont des groupes finis. Par le th´ eor` eme de Lagrange, le
nombre d’´ el´ ements de H divise le nombre d’´ el´ ements de G. Deux cas sont possibles. Soit
H = G, auquel cas |H| = |G|. Sinon, |H| est un diviseur strict de |G|. En particulier,
|H| ≤
|G|
2 . On peut cependant montrer qu’il existe a ∈ G tel que J(a, n) n’est pas
congru `
a a
n−1
2
modulo n, ce qui exclut le cas |H| = |G|. Cette preuve est avanc´ ee et
nous ne la ferons pas ici.
Alors, |H| ≤
|G|
2 <
n−1
2 .
Th´ eor` eme 7.20 Si n est un nombre premier impair, alors tous les nombres a ∈ E =
{1, . . . , n − 1} r´ eussissent le test, c’est-` a-dire satisfont `
a (7.4).
Nous mettons en ´ evidence sous forme de r´ esultats distincts des parties de la preuve
qui nous seront utiles dans d’autres chapitres.
Lemme 7.21 1. Soient n un nombre premier, S = {0, 1, . . . , n − 1} et P (x) un polynˆ ome
P (x) = x
r + a r−1 x
r−1 + · · · + a 1 x + a 0
tel que a i ∈ S. Alors, il existe au plus r solutions x i ∈ S de la congruence
P (x) ≡ 0 (mod n).
2. Dans le cas particulier du polynˆ ome P d (x) = x
d
− 1 pour d | n − 1, la congruence
P d (x) ≡ 0 (mod n) a exactement d solutions distinctes dans E = S \ {0}.
Preuve 1. La preuve se fait par induction sur r. C’est vrai pour r = 1. Supposons
que ce soit vrai pour tout polynˆ ome de degr´ e r et montrons-le pour un polynˆ ome
P (x) de degr´ e r + 1. Supposons qu’il existe a 1 ∈ E tel que P (a 1 ) ≡ 0 (mod n).
Divisons le polynˆ ome P (x) par x − a 1 . Nous obtenons
P (x) = (x − a 1 )Q(x) + β,
o` u Q(x) est un polynˆ ome de degr´ e r ` a coefficients dans Z. Soit
Q(x) = x
r + b r−1 x
r−1 + · · · + b 1 x + b 0 ,
et soient b i ≡ c i (mod n) et β ≡ γ (mod n) pour c i , γ ∈ S. Posons