234
7 La cryptographie ` a cl´ e publique
´ el´ ements de E dont l’ordre divise p
ki
i . Si toutes les solutions de Q p
k i
i
(x) ≡ 0 (mod n) dans
E correspondaient ` a des ´ el´ ements du groupe d’ordre inf´ erieur ` a p
ki
i , leur ordre diviserait
p
ki−1
i
. Ces ´ el´ ements seraient donc des solutions de la congruence Q p
k i −1
i
(x) = x
p
k i −1
i
−
1 ≡ 0 (mod n). Il y aurait contradiction, car Q p
k i −1
i
(x) ≡ 0 (mod n) a exactement p
ki−1
i
solutions dans E. Soit donc g i ∈ E, une solution de Q p
k i
i
(x) ≡ 0 (mod n) correspondant
` a un ´ el´ ement du groupe d’ordre p
ki
i . Alors, on v´ erifie facilement que
g = g 1 . . . g s
est d’ordre p
k1
1 . . . p
ks
s = n − 1. Ceci est une cons´ equence du lemme suivant.
Lemme 7.23 Soit G un groupe fini dans lequel l’op´ eration est commutative. Si g 1 est
d’ordre m 1 , que g 2 est d’ordre m 2 et que (m 1 , m 2 ) = 1, alors g 1 g 2 est d’ordre m 1 m 2 .
Preuve Soit m l’ordre de g 1 g 2 . On a (g 1 g 2 )
m1m2 = (g
m1
1 )
m2 (g
m2
2 )
m1 = 1. Donc,
m | m 1 m 2 . Puisque m | m 1 m 2 , on peut ´ ecrire m comme suit : m = n 1 n 2 pour n 1 =
(m 1 , m) | m 1 et n 2 = (m 2 , m) | m 2 (exercice : v´ erifier !). Ceci permet d’´ ecrire m i sous
la forme m i = n i r i . On a
g
mr1
1
= g
n1n2r1
1
= (g
m1
1 )
n2 = 1.
Puisque (g 1 g 2 )
m = 1, on a g
m
1 = g
−m
2 , donc on a aussi g
−mr1
2
= 1, ce qui entraˆ ıne
g
mr1
2
= 1. Mais
g
mr1
2
= g
n1n2r1
2
= g
m1n2
2
.
On doit donc avoir m 2 | m 1 n 2 . Puisque (m 2 , m 1 ) = 1, ceci entraˆ ıne m 2 | n 2 . Comme
d´ ej` a n 2 | m 2 , on a finalement m 2 = n 2 . De mˆ eme, on peut v´ erifier que m 1 = n 1 . Donc,
m = m 1 m 2 .
Preuve du th´ eor` eme 7.20 Il suffit de v´ erifier que tous les a satisfont `
a J(a, n) ≡
a
n−1
2
(mod n). Pour a, on a deux possibilit´ es.
Si a est un r´ esidu quadratique, c’est-` a-dire qu’il existe x ∈ E tel que x
2
≡ a (mod n),
alors par d´ efinition J(a, n) = 1. D’autre part, a
n−1
2
≡ x
n−1
≡ 1 (mod n) de par le petit
th´ eor` eme de Fermat (th´ eor` eme 7.9).
Le deuxi` eme cas (a n’est pas un r´ esidu quadratique) demande un peu plus de travail.
Dans ce cas, on a J(a, n) = −1 par d´ efinition. On va montrer que a
n−1
2
≡ −1 (mod n).
Nous avons montr´ e au th´ eor` eme 7.22 qu’il existe un ´ el´ ement g ∈ E tel que E =
{g, g
2 , . . . , g
n−1 = 1}. Comme g
n−1 = 1, alors chaque ´ el´ ement a ∈ E satisfait ` a a
n−1 =
1, c’est-` a-dire est solution de la congruence x
n−1
− 1 ≡ 0 (mod n). Remarquons que
x
n−1
− 1 =
x
n−1
2
− 1
x
n−1
2
+ 1
.
Nous avons vu dans la preuve du th´ eor` eme 7.22 qu’une congruence P (x) ≡ 0 (mod n)
a au plus
n−1
2 racines dans E quand P (x) est un polynˆ ome de degr´ e
n−1
2 .
7 La cryptographie ` a cl´ e publique
´ el´ ements de E dont l’ordre divise p
ki
i . Si toutes les solutions de Q p
k i
i
(x) ≡ 0 (mod n) dans
E correspondaient ` a des ´ el´ ements du groupe d’ordre inf´ erieur ` a p
ki
i , leur ordre diviserait
p
ki−1
i
. Ces ´ el´ ements seraient donc des solutions de la congruence Q p
k i −1
i
(x) = x
p
k i −1
i
−
1 ≡ 0 (mod n). Il y aurait contradiction, car Q p
k i −1
i
(x) ≡ 0 (mod n) a exactement p
ki−1
i
solutions dans E. Soit donc g i ∈ E, une solution de Q p
k i
i
(x) ≡ 0 (mod n) correspondant
` a un ´ el´ ement du groupe d’ordre p
ki
i . Alors, on v´ erifie facilement que
g = g 1 . . . g s
est d’ordre p
k1
1 . . . p
ks
s = n − 1. Ceci est une cons´ equence du lemme suivant.
Lemme 7.23 Soit G un groupe fini dans lequel l’op´ eration est commutative. Si g 1 est
d’ordre m 1 , que g 2 est d’ordre m 2 et que (m 1 , m 2 ) = 1, alors g 1 g 2 est d’ordre m 1 m 2 .
Preuve Soit m l’ordre de g 1 g 2 . On a (g 1 g 2 )
m1m2 = (g
m1
1 )
m2 (g
m2
2 )
m1 = 1. Donc,
m | m 1 m 2 . Puisque m | m 1 m 2 , on peut ´ ecrire m comme suit : m = n 1 n 2 pour n 1 =
(m 1 , m) | m 1 et n 2 = (m 2 , m) | m 2 (exercice : v´ erifier !). Ceci permet d’´ ecrire m i sous
la forme m i = n i r i . On a
g
mr1
1
= g
n1n2r1
1
= (g
m1
1 )
n2 = 1.
Puisque (g 1 g 2 )
m = 1, on a g
m
1 = g
−m
2 , donc on a aussi g
−mr1
2
= 1, ce qui entraˆ ıne
g
mr1
2
= 1. Mais
g
mr1
2
= g
n1n2r1
2
= g
m1n2
2
.
On doit donc avoir m 2 | m 1 n 2 . Puisque (m 2 , m 1 ) = 1, ceci entraˆ ıne m 2 | n 2 . Comme
d´ ej` a n 2 | m 2 , on a finalement m 2 = n 2 . De mˆ eme, on peut v´ erifier que m 1 = n 1 . Donc,
m = m 1 m 2 .
Preuve du th´ eor` eme 7.20 Il suffit de v´ erifier que tous les a satisfont `
a J(a, n) ≡
a
n−1
2
(mod n). Pour a, on a deux possibilit´ es.
Si a est un r´ esidu quadratique, c’est-` a-dire qu’il existe x ∈ E tel que x
2
≡ a (mod n),
alors par d´ efinition J(a, n) = 1. D’autre part, a
n−1
2
≡ x
n−1
≡ 1 (mod n) de par le petit
th´ eor` eme de Fermat (th´ eor` eme 7.9).
Le deuxi` eme cas (a n’est pas un r´ esidu quadratique) demande un peu plus de travail.
Dans ce cas, on a J(a, n) = −1 par d´ efinition. On va montrer que a
n−1
2
≡ −1 (mod n).
Nous avons montr´ e au th´ eor` eme 7.22 qu’il existe un ´ el´ ement g ∈ E tel que E =
{g, g
2 , . . . , g
n−1 = 1}. Comme g
n−1 = 1, alors chaque ´ el´ ement a ∈ E satisfait ` a a
n−1 =
1, c’est-` a-dire est solution de la congruence x
n−1
− 1 ≡ 0 (mod n). Remarquons que
x
n−1
− 1 =
x
n−1
2
− 1
x
n−1
2
+ 1
.
Nous avons vu dans la preuve du th´ eor` eme 7.22 qu’une congruence P (x) ≡ 0 (mod n)
a au plus
n−1
2 racines dans E quand P (x) est un polynˆ ome de degr´ e
n−1
2 .