242
7 La cryptographie ` a cl´ e publique
e · d ≡ 1 (mod φ(n)).
12. On se donne un nombre entier de N chiffres. Soit a N −1 . . . a 1 a 0 sa repr´ esentation
d´ ecimale, c’est-` a-dire
N = a N −1 10
N −1 + a N −2 10
N −2
· · · + a 1 10 + a 0 .
a) Montrer que N est divisible par 11 si et seulement si
a 0 − a 1 + a 2 − a 3 + · · · + (−1)
N −2 a N −2 + (−1)
N −1 a N −1 ≡ 0 (mod 11).
(Suggestion : consid´ erer 10
i (mod 11).)
Remarque : lors de la recherche de nombres premiers, ceci permet d’´ ecrire un test
simple permettant d’´ eliminer tous les multiples de 11.
b) Montrer que N est divisible par 101 si et seulement si
−(a 0 + 10a 1 ) + (a 2 + 10a 3 ) − (a 4 + 10a 5 ) + (a 6 + 10a 7 ) · · · ≡ 0 (mod 101)
13. Montrer que n est premier si et seulement si
(x + 1)
n
≡ x
n + 1 (mod n).
Remarque : cet exercice constitue l’id´ ee centrale de l’algorithme AKS [1].
14. On consid` ere les ensembles E n = {0, 1, . . . , n − 1} pour n ∈ N. Soient p et q tels
que (p, q) = 1. On d´ efinit la fonction : F : E pq → E p × E q par F (n) = (n 1 , n 2 ) o` u
n ≡ n 1 (mod p) et n ≡ n 2 (mod q). Montrer que F est une bijection. (Ce r´ esultat
est la formulation moderne de ce qu’on appelle le « th´ eor` eme chinois des restes ».)
15. D´ emontrer le th´ eor` eme de Wilson : n est premier si et seulement si n divise
(n − 1)! + 1. (Un sens est plus difficile. Si n est premier, il faut se servir du fait que
{1, . . . , n−1} est un groupe pour la multiplication pour montrer que n | (n−1)!+1.)
Remarque : ce th´ eor` eme donne un test pour d´ ecider si n est premier. Cependant,
ce test n’est pas int´ eressant en pratique parce que le calcul de (n − 1)! est hors de
port´ ee des ordinateurs si n est un grand nombre.
16. Montrer que les exposants
b
2 −1
8
et
(a−1)(b−1)
4
dans la formule (7.5) donnant J(a, b)
sont toujours des entiers pour a, b impairs.
7 La cryptographie ` a cl´ e publique
e · d ≡ 1 (mod φ(n)).
12. On se donne un nombre entier de N chiffres. Soit a N −1 . . . a 1 a 0 sa repr´ esentation
d´ ecimale, c’est-` a-dire
N = a N −1 10
N −1 + a N −2 10
N −2
· · · + a 1 10 + a 0 .
a) Montrer que N est divisible par 11 si et seulement si
a 0 − a 1 + a 2 − a 3 + · · · + (−1)
N −2 a N −2 + (−1)
N −1 a N −1 ≡ 0 (mod 11).
(Suggestion : consid´ erer 10
i (mod 11).)
Remarque : lors de la recherche de nombres premiers, ceci permet d’´ ecrire un test
simple permettant d’´ eliminer tous les multiples de 11.
b) Montrer que N est divisible par 101 si et seulement si
−(a 0 + 10a 1 ) + (a 2 + 10a 3 ) − (a 4 + 10a 5 ) + (a 6 + 10a 7 ) · · · ≡ 0 (mod 101)
13. Montrer que n est premier si et seulement si
(x + 1)
n
≡ x
n + 1 (mod n).
Remarque : cet exercice constitue l’id´ ee centrale de l’algorithme AKS [1].
14. On consid` ere les ensembles E n = {0, 1, . . . , n − 1} pour n ∈ N. Soient p et q tels
que (p, q) = 1. On d´ efinit la fonction : F : E pq → E p × E q par F (n) = (n 1 , n 2 ) o` u
n ≡ n 1 (mod p) et n ≡ n 2 (mod q). Montrer que F est une bijection. (Ce r´ esultat
est la formulation moderne de ce qu’on appelle le « th´ eor` eme chinois des restes ».)
15. D´ emontrer le th´ eor` eme de Wilson : n est premier si et seulement si n divise
(n − 1)! + 1. (Un sens est plus difficile. Si n est premier, il faut se servir du fait que
{1, . . . , n−1} est un groupe pour la multiplication pour montrer que n | (n−1)!+1.)
Remarque : ce th´ eor` eme donne un test pour d´ ecider si n est premier. Cependant,
ce test n’est pas int´ eressant en pratique parce que le calcul de (n − 1)! est hors de
port´ ee des ordinateurs si n est un grand nombre.
16. Montrer que les exposants
b
2 −1
8
et
(a−1)(b−1)
4
dans la formule (7.5) donnant J(a, b)
sont toujours des entiers pour a, b impairs.