226
7 La cryptographie ` a cl´ e publique
Remarque La preuve de ce th´ eor` eme est d’un niveau tr` es avanc´ e et ne sera pas
pr´ esent´ ee ici.
On veut construire de grands nombres premiers. Supposons pour le moment qu’on
connaisse un test permettant de d´ eterminer si un grand nombre est premier. On pourrait
vouloir choisir au hasard un grand nombre n et tester s’il est premier. S’il n’est pas
premier, on testera si n + 1 est premier, etc. jusqu’` a ce qu’on tombe sur un nombre
premier. Nous allons montrer que ce n’est pas une bonne m´ ethode.
Th´ eor` eme 7.13 Il existe des suites arbitrairement longues de nombres entiers cons´ ecutifs qui ne sont pas premiers.
Preuve Soit n ∈ N. La suite
n! + 2, n! + 3, . . . , n! + n
est une suite de n − 1 nombres cons´ ecutifs non premiers. En effet, soit 1 < m ≤ n. Alors,
m | n!. Donc, m | n! + m.
La bonne technique est plutˆ ot de choisir au hasard des grands nombres et de tester
s’ils sont premiers. La th´ eorie des probabilit´ es assure que, si les choix sont ind´ ependants,
on va tomber sur un nombre premier en un nombre raisonnable d’essais.
Consid´ erons l’ensemble des entiers F = {1, . . . , N} tel que N est grand. Si on veut
obtenir des entiers de 100 (respectivement 200) chiffres, on va prendre N = 10
100 (respectivement N = 10
200 ). Par le th´ eor` eme des nombres premiers, le nombre d’entiers de
F qui sont premiers est de l’ordre de π(N ) =
N
ln N . Donc, si on choisit au hasard un
nombre n dans F , on peut calculer approximativement la probabilit´ e que n soit premier.
On a
Prob(n premier) ≈
N
ln N
N
=
1
ln N
.
Si N = 10
100 , alors ln N = 100 ln 10 = 100 × 2,30259 = 230,259. Donc, en prenant au
hasard un nombre de 100 chiffres, on a environ une chance sur 230 d’obtenir un nombre
premier. On peut am´ eliorer grandement ces chances en choisissant au hasard un nombre
impair (il suffit de choisir au hasard le dernier chiffre dans l’ensemble {1, 3, 5, 7, 9}). La
probabilit´ e de trouver un nombre premier est alors d’une sur 115. Si on avait choisi le
dernier chiffre dans {1, 3, 7, 9} (on aurait ´ elimin´ e ainsi les multiples de 5), elle serait
devenue d’une sur 92.
Soit B l’ensemble des nombres impairs de F qui ne sont pas divisibles par 5. Cet
ensemble contient environ
2N
5 ´ el´ ements. Soit p =
5
2 ln N . Chaque fois qu’on choisit au
hasard un nombre de B, on a une probabilit´ e p que le nombre soit premier. On appelle
« exp´ erience al´ eatoire » le fait de choisir au hasard un nombre de B et de tester s’il
est premier. On r´ ep` ete l’exp´ erience al´ eatoire de mani` ere ind´ ependante jusqu’` a ce qu’on
tombe sur un nombre premier. Soit X le nombre d’exp´ eriences n´ ecessaires. Alors, X est
une variable al´ eatoire de type g´ eom´ etrique de param` etre p. On a donc
7 La cryptographie ` a cl´ e publique
Remarque La preuve de ce th´ eor` eme est d’un niveau tr` es avanc´ e et ne sera pas
pr´ esent´ ee ici.
On veut construire de grands nombres premiers. Supposons pour le moment qu’on
connaisse un test permettant de d´ eterminer si un grand nombre est premier. On pourrait
vouloir choisir au hasard un grand nombre n et tester s’il est premier. S’il n’est pas
premier, on testera si n + 1 est premier, etc. jusqu’` a ce qu’on tombe sur un nombre
premier. Nous allons montrer que ce n’est pas une bonne m´ ethode.
Th´ eor` eme 7.13 Il existe des suites arbitrairement longues de nombres entiers cons´ ecutifs qui ne sont pas premiers.
Preuve Soit n ∈ N. La suite
n! + 2, n! + 3, . . . , n! + n
est une suite de n − 1 nombres cons´ ecutifs non premiers. En effet, soit 1 < m ≤ n. Alors,
m | n!. Donc, m | n! + m.
La bonne technique est plutˆ ot de choisir au hasard des grands nombres et de tester
s’ils sont premiers. La th´ eorie des probabilit´ es assure que, si les choix sont ind´ ependants,
on va tomber sur un nombre premier en un nombre raisonnable d’essais.
Consid´ erons l’ensemble des entiers F = {1, . . . , N} tel que N est grand. Si on veut
obtenir des entiers de 100 (respectivement 200) chiffres, on va prendre N = 10
100 (respectivement N = 10
200 ). Par le th´ eor` eme des nombres premiers, le nombre d’entiers de
F qui sont premiers est de l’ordre de π(N ) =
N
ln N . Donc, si on choisit au hasard un
nombre n dans F , on peut calculer approximativement la probabilit´ e que n soit premier.
On a
Prob(n premier) ≈
N
ln N
N
=
1
ln N
.
Si N = 10
100 , alors ln N = 100 ln 10 = 100 × 2,30259 = 230,259. Donc, en prenant au
hasard un nombre de 100 chiffres, on a environ une chance sur 230 d’obtenir un nombre
premier. On peut am´ eliorer grandement ces chances en choisissant au hasard un nombre
impair (il suffit de choisir au hasard le dernier chiffre dans l’ensemble {1, 3, 5, 7, 9}). La
probabilit´ e de trouver un nombre premier est alors d’une sur 115. Si on avait choisi le
dernier chiffre dans {1, 3, 7, 9} (on aurait ´ elimin´ e ainsi les multiples de 5), elle serait
devenue d’une sur 92.
Soit B l’ensemble des nombres impairs de F qui ne sont pas divisibles par 5. Cet
ensemble contient environ
2N
5 ´ el´ ements. Soit p =
5
2 ln N . Chaque fois qu’on choisit au
hasard un nombre de B, on a une probabilit´ e p que le nombre soit premier. On appelle
« exp´ erience al´ eatoire » le fait de choisir au hasard un nombre de B et de tester s’il
est premier. On r´ ep` ete l’exp´ erience al´ eatoire de mani` ere ind´ ependante jusqu’` a ce qu’on
tombe sur un nombre premier. Soit X le nombre d’exp´ eriences n´ ecessaires. Alors, X est
une variable al´ eatoire de type g´ eom´ etrique de param` etre p. On a donc