236
7 La cryptographie ` a cl´ e publique
`
A titre d’information, l’algorithme probabiliste d´ ecrit pr´ ec´ edemment fonctionne en
temps polynomial, de mˆ eme que le nouvel algorithme AKS. C’est pourquoi il est beaucoup plus facile pour un ordinateur de construire de grands nombres premiers que de
factoriser de grands nombres entiers.
Nous allons commencer par nous convaincre que les raffinements de l’algorithme
classique de factorisation ne permettent pas de diminuer significativement le temps de
factorisation. On consid` ere un nombre n de 200 chiffres, c’est-` a-dire un nombre de l’ordre
de 10
200 . L’algorithme classique consiste ` a chercher s’il existe un diviseur d ≤
√
n. On
doit donc faire de l’ordre de 10
100 essais. Essayons quelques astuces :
• Si on se limite aux nombres impairs, on a m 1 ≈
10
100
2
tests ` a faire.
• Si on se limite `
a des grands diviseurs (des nombres de 100 chiffres), alors on a
m 2 =
9
10 m 1 tests ` a faire (exercice).
• Si on met en parall` ele un milliard d’ordinateurs, on a m 3 = 10
−9 m 2 tests ` a faire.
• Si on met en parall` ele un milliard de superordinateurs de 5000 processeurs pouvant faire 5000 op´ erations en parall` ele (c’´ etait la puissance maximum des superordinateurs en 2004), on limite le nombre d’op´ erations successives ` a m 4 =
m3
5000 .
• Dans ce dernier cas, on aurait encore m 5 ≥ 10
86 op´ erations successives ` a faire.
Trop !
Supposons qu’on arrive ` a s’approcher avec d’autres astuces d’une factorisation de la
cl´ e, alors il suffit d’allonger la cl´ e de quelques dizaines de chiffres pour voir ces efforts
an´ eantis.
On voit donc que, pour factoriser des grands nombres, il nous faut absolument de
meilleurs algorithmes. Tel que mentionn´ e plus haut, il existe de bien meilleurs algorithmes, et certains fonctionnent en temps sous-exponentiel. L’algorithme de Shor introduit en 1997 permet de factoriser des nombres entiers. Cet algorithme fonctionne en
temps exponentiel sur un ordinateur classique, mais en temps polynomial sur un ordinateur quantique. C’est un algorithme probabiliste : si n n’est pas premier, l’algorithme
a une tr` es grande probabilit´ e de trouver un diviseur d de n en temps polynomial. Nous
nous contenterons de donner les grandes lignes de cet algorithme, sans en montrer tous
les d´ etails.
Le principe de l’algorithme de Shor ([5], [8]) L’id´ ee de base de l’algorithme est
de trouver un diviseur d de n. Une fois qu’on a pu ´ ecrire n = dm, on teste si d et m
sont premiers. Si au moins un des deux n’est pas premier, on it` ere en r´ eappliquant la
mˆ eme m´ ethode ` a d et ` a m. On s’arrˆ ete quand tous les facteurs sont premiers. Au fur et
` a mesure qu’on it` ere, les calculs deviennent plus faciles, car d et m sont plus petits que
n.
La m´ ethode On cherche un entier r tel que n | r
2
− 1, mais tel que ni r − 1, ni r + 1
ne soient divisibles par n.
Trouver un tel r permet de trouver un diviseur propre de n. En effet, r
2
− 1 ≡
0 (mod n), ce qui implique que (r − 1)(r + 1) = mn pour un entier m. Alors, si p
est un facteur premier de n, n´ ecessairement p | r − 1 ou p | r + 1. Si p | r − 1, alors
7 La cryptographie ` a cl´ e publique
`
A titre d’information, l’algorithme probabiliste d´ ecrit pr´ ec´ edemment fonctionne en
temps polynomial, de mˆ eme que le nouvel algorithme AKS. C’est pourquoi il est beaucoup plus facile pour un ordinateur de construire de grands nombres premiers que de
factoriser de grands nombres entiers.
Nous allons commencer par nous convaincre que les raffinements de l’algorithme
classique de factorisation ne permettent pas de diminuer significativement le temps de
factorisation. On consid` ere un nombre n de 200 chiffres, c’est-` a-dire un nombre de l’ordre
de 10
200 . L’algorithme classique consiste ` a chercher s’il existe un diviseur d ≤
√
n. On
doit donc faire de l’ordre de 10
100 essais. Essayons quelques astuces :
• Si on se limite aux nombres impairs, on a m 1 ≈
10
100
2
tests ` a faire.
• Si on se limite `
a des grands diviseurs (des nombres de 100 chiffres), alors on a
m 2 =
9
10 m 1 tests ` a faire (exercice).
• Si on met en parall` ele un milliard d’ordinateurs, on a m 3 = 10
−9 m 2 tests ` a faire.
• Si on met en parall` ele un milliard de superordinateurs de 5000 processeurs pouvant faire 5000 op´ erations en parall` ele (c’´ etait la puissance maximum des superordinateurs en 2004), on limite le nombre d’op´ erations successives ` a m 4 =
m3
5000 .
• Dans ce dernier cas, on aurait encore m 5 ≥ 10
86 op´ erations successives ` a faire.
Trop !
Supposons qu’on arrive ` a s’approcher avec d’autres astuces d’une factorisation de la
cl´ e, alors il suffit d’allonger la cl´ e de quelques dizaines de chiffres pour voir ces efforts
an´ eantis.
On voit donc que, pour factoriser des grands nombres, il nous faut absolument de
meilleurs algorithmes. Tel que mentionn´ e plus haut, il existe de bien meilleurs algorithmes, et certains fonctionnent en temps sous-exponentiel. L’algorithme de Shor introduit en 1997 permet de factoriser des nombres entiers. Cet algorithme fonctionne en
temps exponentiel sur un ordinateur classique, mais en temps polynomial sur un ordinateur quantique. C’est un algorithme probabiliste : si n n’est pas premier, l’algorithme
a une tr` es grande probabilit´ e de trouver un diviseur d de n en temps polynomial. Nous
nous contenterons de donner les grandes lignes de cet algorithme, sans en montrer tous
les d´ etails.
Le principe de l’algorithme de Shor ([5], [8]) L’id´ ee de base de l’algorithme est
de trouver un diviseur d de n. Une fois qu’on a pu ´ ecrire n = dm, on teste si d et m
sont premiers. Si au moins un des deux n’est pas premier, on it` ere en r´ eappliquant la
mˆ eme m´ ethode ` a d et ` a m. On s’arrˆ ete quand tous les facteurs sont premiers. Au fur et
` a mesure qu’on it` ere, les calculs deviennent plus faciles, car d et m sont plus petits que
n.
La m´ ethode On cherche un entier r tel que n | r
2
− 1, mais tel que ni r − 1, ni r + 1
ne soient divisibles par n.
Trouver un tel r permet de trouver un diviseur propre de n. En effet, r
2
− 1 ≡
0 (mod n), ce qui implique que (r − 1)(r + 1) = mn pour un entier m. Alors, si p
est un facteur premier de n, n´ ecessairement p | r − 1 ou p | r + 1. Si p | r − 1, alors