230
7 La cryptographie ` a cl´ e publique
Le calcul peut sembler long et fastidieux. Mais ce qui est important c’est que, pour un
ordinateur, c’est un calcul simple.
Pour v´ erifier si a passe le test, on doit maintenant calculer a
b−1
2
(mod b). On a
b−1
2 = 103. Nous avons d´ ej` a vu comment ´ evaluer 130
103 . On d´ ecompose
b−1
2 = 103 en
puissances de 2 : 103 = 64 + 32 + 4 + 2 + 1 = 1 + 2
1 + 2
2 + 2
5 + 2
6 . On calcule
130
2
= 16900 ≡ 133 (mod 207),
130
4
= (130
2 )
2
≡ 133
2 = 17689 ≡ 94 (mod 207),
130
8
= (130
4 )
2
≡ 94
2 = 8836 ≡ 142 (mod 207),
130
16 = (130
8 )
2
≡ 142
2 = 20164 ≡ 85 (mod 207),
130
32 = (130
16 )
2
≡ 85
2 = 7225 ≡ 187 (mod 207),
130
64 = (130
32 )
2
≡ 187
2 = 34969 ≡ 193 (mod 207).
Maintenant
130
103 = 130
64
× 130
32
× 130
4
× 130
2
× 130
≡ 193 × 187 × 94 × 133 × 130 (mod 207)
≡ 67 (mod 207).
On voit que J(130, 207) = 130
207−1
2
. On en conclut que 207 n’est pas premier. Ici, c’´ etait
facile `
a voir : 207 = 3
2
· 23.
Dans la pr´ esentation de notre test de primalit´ e, nous avons affirm´ e que, si n n’est
pas premier, alors moins de la moiti´ e des ´ el´ ements de E r´ eussissent le test, tandis que
si n est premier, la totalit´ e des ´ el´ ements de E passent le test. Nous allons esquisser la
preuve du premier r´ esultat et montrer le deuxi` eme. Cette partie est avanc´ ee. Elle fait
appel `
a des notions de th´ eorie des groupes finis.
D´ efinition 7.16 1. Un ensemble G muni d’une op´ eration ∗ est un groupe si
• l’op´ eration ∗ est associative, c’est-` a-dire
∀a, b, c ∈ G, (a ∗ b) ∗ c = a ∗ (b ∗ c);
• il existe un ´ el´ ement neutre 1 ∈ G tel que
∀a ∈ G, 1 ∗ a = a ∗ 1 = a;
• tout ´ el´ ement a un inverse, c’est-` a-dire
∀a ∈ G, ∃b ∈ G, a ∗ b = b ∗ a = 1.
2. Un sous-ensemble H ⊂ G de G est un sous-groupe de G si H, muni de l’op´ eration
∗, est un groupe.
3. Un groupe est cyclique s’il existe un ´ el´ ement g ∈ G tel que tout ´ el´ ement a du groupe
est de la forme a = g
m pour un entier m ∈ Z, o` u on note
7 La cryptographie ` a cl´ e publique
Le calcul peut sembler long et fastidieux. Mais ce qui est important c’est que, pour un
ordinateur, c’est un calcul simple.
Pour v´ erifier si a passe le test, on doit maintenant calculer a
b−1
2
(mod b). On a
b−1
2 = 103. Nous avons d´ ej` a vu comment ´ evaluer 130
103 . On d´ ecompose
b−1
2 = 103 en
puissances de 2 : 103 = 64 + 32 + 4 + 2 + 1 = 1 + 2
1 + 2
2 + 2
5 + 2
6 . On calcule
130
2
= 16900 ≡ 133 (mod 207),
130
4
= (130
2 )
2
≡ 133
2 = 17689 ≡ 94 (mod 207),
130
8
= (130
4 )
2
≡ 94
2 = 8836 ≡ 142 (mod 207),
130
16 = (130
8 )
2
≡ 142
2 = 20164 ≡ 85 (mod 207),
130
32 = (130
16 )
2
≡ 85
2 = 7225 ≡ 187 (mod 207),
130
64 = (130
32 )
2
≡ 187
2 = 34969 ≡ 193 (mod 207).
Maintenant
130
103 = 130
64
× 130
32
× 130
4
× 130
2
× 130
≡ 193 × 187 × 94 × 133 × 130 (mod 207)
≡ 67 (mod 207).
On voit que J(130, 207) = 130
207−1
2
. On en conclut que 207 n’est pas premier. Ici, c’´ etait
facile `
a voir : 207 = 3
2
· 23.
Dans la pr´ esentation de notre test de primalit´ e, nous avons affirm´ e que, si n n’est
pas premier, alors moins de la moiti´ e des ´ el´ ements de E r´ eussissent le test, tandis que
si n est premier, la totalit´ e des ´ el´ ements de E passent le test. Nous allons esquisser la
preuve du premier r´ esultat et montrer le deuxi` eme. Cette partie est avanc´ ee. Elle fait
appel `
a des notions de th´ eorie des groupes finis.
D´ efinition 7.16 1. Un ensemble G muni d’une op´ eration ∗ est un groupe si
• l’op´ eration ∗ est associative, c’est-` a-dire
∀a, b, c ∈ G, (a ∗ b) ∗ c = a ∗ (b ∗ c);
• il existe un ´ el´ ement neutre 1 ∈ G tel que
∀a ∈ G, 1 ∗ a = a ∗ 1 = a;
• tout ´ el´ ement a un inverse, c’est-` a-dire
∀a ∈ G, ∃b ∈ G, a ∗ b = b ∗ a = 1.
2. Un sous-ensemble H ⊂ G de G est un sous-groupe de G si H, muni de l’op´ eration
∗, est un groupe.
3. Un groupe est cyclique s’il existe un ´ el´ ement g ∈ G tel que tout ´ el´ ement a du groupe
est de la forme a = g
m pour un entier m ∈ Z, o` u on note