7.5 L’algorithme de Shor
235
Il est ´ evident que 1, g
2 , g
4 , . . . , g
2k , . . . sont des r´ esidus quadratiques. Ce sont les
solutions de x
n−1
2
− 1 ≡ 0 (mod n). Donc, les nombres g, g
3 , . . . , g
2k+1 , . . . sont les
solutions de x
n−1
2
≡ −1 (mod n). V´ erifions que ces nombres ne peuvent ˆ etre des r´ esidus
quadratiques. En effet, si g
2k+1
≡ y
2 (mod n) pour y ∈ E, on aurait (g
2k+1 )
n−1
2
≡
(y
2 )
n−1
2
≡ y
n−1
≡ 1 (mod n). Ceci est une contradiction, car (g
2k+1 )
n−1
2
≡ −1 (mod n).
Un algorithme d´ eterministe de primalit´ e L’algorithme que nous venons de d´ ecrire
pour tester si un nombre est premier est un algorithme probabiliste. En effet, il permet de
d´ eterminer si un nombre n’est pas premier, mais il ne permet jamais d’ˆ etre compl` etement
certain en un temps raisonnable qu’un nombre est premier : il faudrait faire le test sur
plus de la moiti´ e des entiers inf´ erieurs `
a n.
En 2003, Agrawal, Kayal et Saxena annon¸ caient un nouvel algorithme d´ eterministe,
appel´ e algorithme AKS, permettant de tester si un nombre est premier en un temps
raisonnable : l’article n’est paru qu’en 2004 [1]. Cet algorithme est beaucoup moins
rapide que les algorithmes probabilistes, mais son int´ erˆ et th´ eorique est grand : il r´ epond
` a une question pos´ ee par Gauss il y a 200 ans. Il est difficile de le r´ esumer en quelques
lignes, mais l’´ etudier en d´ etail est un bon projet de session `
a condition d’avoir des
notions de th´ eorie des nombres.
7.5 Casser le code RSA : l’algorithme de Shor pour factoriser
de grands nombres
Comme nous l’avons d´ ej` a mentionn´ e, il se fait beaucoup de recherche pour trouver de
meilleurs algorithmes pour factoriser de grands entiers. Pour les informaticiens, un bon
algorithme est un algorithme qui fonctionne en « temps polynomial » (nous d´ efinirons
ce concept ci-dessous). L’introduction par Shor en 1997 d’un algorithme pouvant factoriser de grands nombres entiers en temps polynomial a eu beaucoup de retentissement.
Mais . . . cet algorithme fonctionne sur un ordinateur quantique ; mˆ eme si l’ordinateur
quantique n’est plus compl` etement une fiction, il n’est pas encore une r´ ealit´ e non plus.
Avant d’examiner cet algorithme, parlons un peu de la taille d’un algorithme.
Complexit´ e d’un algorithme appliqu´ e ` a un entier n de m chiffres On a alors
n ≈ 10
m .
Le nombre m est la « taille » de notre entier. La complexit´ e de l’algorithme est
le nombre d’op´ erations que doit effectuer l’ordinateur pour ex´ ecuter l’algorithme. Ce
nombre d’op´ erations d´ epend de la taille de l’entier.
Si le nombre d’op´ erations est de l’ordre de Cm
r o` u r est un entier, on dit que
l’algorithme fonctionne en temps polynomial.
L’algorithme classique de factorisation fonctionne en temps exponentiel. En effet, il
requiert de tester si les nombres 1, 2, . . . , d ≤
√
n sont des diviseurs de n. Le nombre de
tests est donc de l’ordre de 10
m/2 . Si m est grand, ce nombre devient vite trop grand
pour l’ordinateur.
235
Il est ´ evident que 1, g
2 , g
4 , . . . , g
2k , . . . sont des r´ esidus quadratiques. Ce sont les
solutions de x
n−1
2
− 1 ≡ 0 (mod n). Donc, les nombres g, g
3 , . . . , g
2k+1 , . . . sont les
solutions de x
n−1
2
≡ −1 (mod n). V´ erifions que ces nombres ne peuvent ˆ etre des r´ esidus
quadratiques. En effet, si g
2k+1
≡ y
2 (mod n) pour y ∈ E, on aurait (g
2k+1 )
n−1
2
≡
(y
2 )
n−1
2
≡ y
n−1
≡ 1 (mod n). Ceci est une contradiction, car (g
2k+1 )
n−1
2
≡ −1 (mod n).
Un algorithme d´ eterministe de primalit´ e L’algorithme que nous venons de d´ ecrire
pour tester si un nombre est premier est un algorithme probabiliste. En effet, il permet de
d´ eterminer si un nombre n’est pas premier, mais il ne permet jamais d’ˆ etre compl` etement
certain en un temps raisonnable qu’un nombre est premier : il faudrait faire le test sur
plus de la moiti´ e des entiers inf´ erieurs `
a n.
En 2003, Agrawal, Kayal et Saxena annon¸ caient un nouvel algorithme d´ eterministe,
appel´ e algorithme AKS, permettant de tester si un nombre est premier en un temps
raisonnable : l’article n’est paru qu’en 2004 [1]. Cet algorithme est beaucoup moins
rapide que les algorithmes probabilistes, mais son int´ erˆ et th´ eorique est grand : il r´ epond
` a une question pos´ ee par Gauss il y a 200 ans. Il est difficile de le r´ esumer en quelques
lignes, mais l’´ etudier en d´ etail est un bon projet de session `
a condition d’avoir des
notions de th´ eorie des nombres.
7.5 Casser le code RSA : l’algorithme de Shor pour factoriser
de grands nombres
Comme nous l’avons d´ ej` a mentionn´ e, il se fait beaucoup de recherche pour trouver de
meilleurs algorithmes pour factoriser de grands entiers. Pour les informaticiens, un bon
algorithme est un algorithme qui fonctionne en « temps polynomial » (nous d´ efinirons
ce concept ci-dessous). L’introduction par Shor en 1997 d’un algorithme pouvant factoriser de grands nombres entiers en temps polynomial a eu beaucoup de retentissement.
Mais . . . cet algorithme fonctionne sur un ordinateur quantique ; mˆ eme si l’ordinateur
quantique n’est plus compl` etement une fiction, il n’est pas encore une r´ ealit´ e non plus.
Avant d’examiner cet algorithme, parlons un peu de la taille d’un algorithme.
Complexit´ e d’un algorithme appliqu´ e ` a un entier n de m chiffres On a alors
n ≈ 10
m .
Le nombre m est la « taille » de notre entier. La complexit´ e de l’algorithme est
le nombre d’op´ erations que doit effectuer l’ordinateur pour ex´ ecuter l’algorithme. Ce
nombre d’op´ erations d´ epend de la taille de l’entier.
Si le nombre d’op´ erations est de l’ordre de Cm
r o` u r est un entier, on dit que
l’algorithme fonctionne en temps polynomial.
L’algorithme classique de factorisation fonctionne en temps exponentiel. En effet, il
requiert de tester si les nombres 1, 2, . . . , d ≤
√
n sont des diviseurs de n. Le nombre de
tests est donc de l’ordre de 10
m/2 . Si m est grand, ce nombre devient vite trop grand
pour l’ordinateur.