7.6 Exercices
239
a) Montrer que si m = p 1 . . . p k o` u p 1 , . . . , p k sont des nombres premiers distincts,
alors φ(m) = (p 1 − 1) . . . (p k − 1).
b) Soit p un nombre premier. Montrer que
φ(p
n ) = p
n
− p
n−1 .
3. Le principe de la cryptographie `
a cl´ e publique fonctionne pour un entier n =
pq, o` u p et q sont deux grands nombres premiers distincts. Est-ce que le principe
fonctionnerait aussi pour un entier de la forme n = p 1 p 2 p 3 o` u p 1 , p 2 , p 3 sont trois
nombres premiers distincts ?
4. Soit p un nombre premier.
a) Calculer φ(p
2 ), o` u φ est la fonction d’Euler.
b) Le principe de la cryptographie `
a cl´ e publique fonctionne pour un entier n =
pq, o` u p et q sont deux grands nombres premiers distincts. Est-ce que le principe
fonctionnerait aussi avec l’entier n = p
2 ? Si oui, d´ ecrire les ´ etapes `
a suivre. Pourquoi
alors ne l’utiliserait-on pas ? On aurait en effet seulement un nombre premier `
a
trouver.
5. Dans un article « grand public » la revue La Recherche donne l’exemple suivant
pour la cryptographie `
a cl´ e publique. On choisit deux nombres premiers p et q
distincts tels que p, q ≡ 2 (mod 3). Soit n = pq. Alice veut envoyer un message `
a
Bob. Son message est un nombre x dans {1, . . . , n − 1} tel que (x, n) = 1 (ce dernier
d´ etail n’apparaˆ ıt pas dans La Recherche !) Pour envoyer son message, Alice calcule
x
3 et divise ensuite ce nombre par n. Soit y ∈ {1, . . . , n − 1} le reste de la division
de x
3 par n (c’est-` a-dire x
3
≡ y (mod n)). Bob d´ ecode avec
d =
2(p − 1)(q − 1) + 1
3
.
Il calcule y
d et le reste z de la division de y
d par n (c’est-` a-dire y
d
≡ z (mod n)) o` u
z ∈ {1, . . . , n − 1}.
a) V´ erifier que d est bien un entier.
b) Expliquer pourquoi y et z ne peuvent s’annuler, c’est-` a-dire qu’on a bien y, z ∈
{1, . . . , n − 1}.
c) Montrer que z = x, c’est-` a-dire que Bob a bien d´ ecod´ e le message d’Alice.
6. Vous voulez vulgariser le syst` eme de cryptographie `
a cl´ e publique. Voici comment
vous vous y prenez : vous choisissez un entier premier p, tel que p ≡ 2 (mod 7) et un
entier premier q, tel que q ≡ 3 (mod 7). Ceci vous permet de calculer n = pq. Vous
expliquez alors comment Alain peut envoyer un message `
a B´ eatrice. Son message
est un nombre m de {1, . . . , n − 1} tel que (m, n) = 1. Pour envoyer son message,
Alain calcule m
7 et divise ensuite ce nombre par n. Soit a ∈ {1, . . . , n−1} le reste de
239
a) Montrer que si m = p 1 . . . p k o` u p 1 , . . . , p k sont des nombres premiers distincts,
alors φ(m) = (p 1 − 1) . . . (p k − 1).
b) Soit p un nombre premier. Montrer que
φ(p
n ) = p
n
− p
n−1 .
3. Le principe de la cryptographie `
a cl´ e publique fonctionne pour un entier n =
pq, o` u p et q sont deux grands nombres premiers distincts. Est-ce que le principe
fonctionnerait aussi pour un entier de la forme n = p 1 p 2 p 3 o` u p 1 , p 2 , p 3 sont trois
nombres premiers distincts ?
4. Soit p un nombre premier.
a) Calculer φ(p
2 ), o` u φ est la fonction d’Euler.
b) Le principe de la cryptographie `
a cl´ e publique fonctionne pour un entier n =
pq, o` u p et q sont deux grands nombres premiers distincts. Est-ce que le principe
fonctionnerait aussi avec l’entier n = p
2 ? Si oui, d´ ecrire les ´ etapes `
a suivre. Pourquoi
alors ne l’utiliserait-on pas ? On aurait en effet seulement un nombre premier `
a
trouver.
5. Dans un article « grand public » la revue La Recherche donne l’exemple suivant
pour la cryptographie `
a cl´ e publique. On choisit deux nombres premiers p et q
distincts tels que p, q ≡ 2 (mod 3). Soit n = pq. Alice veut envoyer un message `
a
Bob. Son message est un nombre x dans {1, . . . , n − 1} tel que (x, n) = 1 (ce dernier
d´ etail n’apparaˆ ıt pas dans La Recherche !) Pour envoyer son message, Alice calcule
x
3 et divise ensuite ce nombre par n. Soit y ∈ {1, . . . , n − 1} le reste de la division
de x
3 par n (c’est-` a-dire x
3
≡ y (mod n)). Bob d´ ecode avec
d =
2(p − 1)(q − 1) + 1
3
.
Il calcule y
d et le reste z de la division de y
d par n (c’est-` a-dire y
d
≡ z (mod n)) o` u
z ∈ {1, . . . , n − 1}.
a) V´ erifier que d est bien un entier.
b) Expliquer pourquoi y et z ne peuvent s’annuler, c’est-` a-dire qu’on a bien y, z ∈
{1, . . . , n − 1}.
c) Montrer que z = x, c’est-` a-dire que Bob a bien d´ ecod´ e le message d’Alice.
6. Vous voulez vulgariser le syst` eme de cryptographie `
a cl´ e publique. Voici comment
vous vous y prenez : vous choisissez un entier premier p, tel que p ≡ 2 (mod 7) et un
entier premier q, tel que q ≡ 3 (mod 7). Ceci vous permet de calculer n = pq. Vous
expliquez alors comment Alain peut envoyer un message `
a B´ eatrice. Son message
est un nombre m de {1, . . . , n − 1} tel que (m, n) = 1. Pour envoyer son message,
Alain calcule m
7 et divise ensuite ce nombre par n. Soit a ∈ {1, . . . , n−1} le reste de