7.6 Exercices
241
a) Coder le mot « MATHS ».
b) Expliquer pourquoi le code est inversible et comment on s’y prend pour d´ ecoder.
c) D´ ecoder le mot « CODE ».
9. La preuve par 9 est une ancienne m´ ethode pour v´ erifier le r´ esultat de la multiplication de deux entiers. Elle ´ etait abondamment enseign´ ee lorsqu’on ne disposait pas
encore de calculatrices. On multiplie deux nombres m et n. Soit N = mn. On veut
v´ erifier le r´ esultat obtenu. Pour cela, on utilise la notation d´ ecimale d’un nombre
M ∈ N : M = a p . . . a 0 o` u a i ∈ {0, 1, . . . 9}. Ceci revient ` a l’´ ecriture
M =
p
i=0
a i 10
i .
Au nombre M , on associe le nombre F (M ) ∈ {0, 1, . . . 8}, o` u F (M ) est le reste de
la division de
p
i=0
a i = a 0 + · · · + a p
par 9. Donnons un exemple. Soit M = 2857. Alors 2 + 8 + 5 + 7 = 22 ≡ 4 (mod 9).
Donc, F (2857) = 4.
Dans la preuve par 9, on calcule F (N ) d’une part. D’autre part, on calcule
F (m), F (n) et le produit r = F (m)F (n). On calcule ensuite F (r).
a) Montrer que, s’il n’y a pas d’erreur de calcul dans la multiplication (c’est-` a-dire
si N = mn), alors on doit avoir
F (N ) = F (r).
Sinon, on conclut qu’il y a une erreur de calcul dans la multiplication (` a condition,
bien sˆ ur, qu’on n’ait pas fait d’erreur dans le calcul des diff´ erents F (M ) !)
b) Donner un exemple simple.
c) Que peut-on dire si F (N ) = F (r) ? Peut-on conclure qu’il n’y a pas eu d’erreur
dans la multiplication N = mn ?
10. Construire un code RSA `
a cl´ e publique avec une cl´ e n = p.q de 60 chiffres. Pour
cela, p et q seront des nombres premiers de 30 chiffres.
a) G´ en´ erer des nombres de 30 chiffres et tester s’ils sont premiers avec un logiciel
de manipulations symboliques.
b) V´ erifier si ces nombres sont premiers en faisant le test de Jacobi ` a l’aide de
nombres a 1 , . . . , a k de moins de 30 chiffres. Faire le test dans le cas d’un nombre
premier et dans le cas d’un nombre non premier. D` es que le test est n´ egatif, on
arrˆ ete et on conclut que le nombre est non premier. Si le test est positif, on continue
pour obtenir une plus grande certitude que le nombre est premier.
11. On se donne un code RSA avec cl´ e n = 23 × 37 = 851 et cl´ e de cryptage e = 47.
Trouver la cl´ e de d´ ecryptage d qui satisfait ` a
241
a) Coder le mot « MATHS ».
b) Expliquer pourquoi le code est inversible et comment on s’y prend pour d´ ecoder.
c) D´ ecoder le mot « CODE ».
9. La preuve par 9 est une ancienne m´ ethode pour v´ erifier le r´ esultat de la multiplication de deux entiers. Elle ´ etait abondamment enseign´ ee lorsqu’on ne disposait pas
encore de calculatrices. On multiplie deux nombres m et n. Soit N = mn. On veut
v´ erifier le r´ esultat obtenu. Pour cela, on utilise la notation d´ ecimale d’un nombre
M ∈ N : M = a p . . . a 0 o` u a i ∈ {0, 1, . . . 9}. Ceci revient ` a l’´ ecriture
M =
p
i=0
a i 10
i .
Au nombre M , on associe le nombre F (M ) ∈ {0, 1, . . . 8}, o` u F (M ) est le reste de
la division de
p
i=0
a i = a 0 + · · · + a p
par 9. Donnons un exemple. Soit M = 2857. Alors 2 + 8 + 5 + 7 = 22 ≡ 4 (mod 9).
Donc, F (2857) = 4.
Dans la preuve par 9, on calcule F (N ) d’une part. D’autre part, on calcule
F (m), F (n) et le produit r = F (m)F (n). On calcule ensuite F (r).
a) Montrer que, s’il n’y a pas d’erreur de calcul dans la multiplication (c’est-` a-dire
si N = mn), alors on doit avoir
F (N ) = F (r).
Sinon, on conclut qu’il y a une erreur de calcul dans la multiplication (` a condition,
bien sˆ ur, qu’on n’ait pas fait d’erreur dans le calcul des diff´ erents F (M ) !)
b) Donner un exemple simple.
c) Que peut-on dire si F (N ) = F (r) ? Peut-on conclure qu’il n’y a pas eu d’erreur
dans la multiplication N = mn ?
10. Construire un code RSA `
a cl´ e publique avec une cl´ e n = p.q de 60 chiffres. Pour
cela, p et q seront des nombres premiers de 30 chiffres.
a) G´ en´ erer des nombres de 30 chiffres et tester s’ils sont premiers avec un logiciel
de manipulations symboliques.
b) V´ erifier si ces nombres sont premiers en faisant le test de Jacobi ` a l’aide de
nombres a 1 , . . . , a k de moins de 30 chiffres. Faire le test dans le cas d’un nombre
premier et dans le cas d’un nombre non premier. D` es que le test est n´ egatif, on
arrˆ ete et on conclut que le nombre est non premier. Si le test est positif, on continue
pour obtenir une plus grande certitude que le nombre est premier.
11. On se donne un code RSA avec cl´ e n = 23 × 37 = 851 et cl´ e de cryptage e = 47.
Trouver la cl´ e de d´ ecryptage d qui satisfait ` a