7.5 L’algorithme de Shor
237
(r − 1, n) = d > 1. Puisque n ne divise pas r − 1, d est un diviseur de n diff´ erent de n.
De mˆ eme si p | r + 1.
Exemple Si n = 65 et r = 14, alors r
2 = 196 = 3 × 65 + 1 ≡ 1 (mod 65) et r − 1 = 13
est un diviseur de 65.
Par contre, si on prend s = 64 ≡ −1 (mod 65), alors s
2
≡ (−1)
2 = 1 (mod 65). On voit
que s + 1 = 65 est divisible par 65. Donc, ce s ne nous est d’aucun secours pour trouver
un diviseur propre de 65.
Comment trouver r ? On prend a au hasard dans E = {1, . . . , n − 1}.
• On commence par calculer (a, n).
• Si (a, n) = d, on a trouv´ e un diviseur de n.
• Si (a, n) = 1, on calcule les puissances de a : a, a
2 , a
3 , . . . On les r´ eduit modulo
n : a
k
≡ a k (mod n), o` u a k ∈ E.
• Comme E est fini, il existe k et l tels que a k = a l . On peut supposer k > l. Alors,
a k−l ≡ a
k−l
≡ 1 (mod n).
• Donc, il existe s minimum tel que a
s
≡ 1 (mod n). Ce nombre s est appel´ e l’ordre
de a. On a s ≤ n.
• Si s est impair, a n’´ etait pas un bon choix. On recommence avec a
= a choisi au
hasard dans E.
• Si s est pair, s = 2m. On prend r ≡ a
m (mod n), o` u r ∈ E. Alors, r
2
≡ a
2m =
a
s
≡ 1 (mod n).
• Si ni r − 1 ni r + 1 ne sont divisibles par n, on a termin´ e. Sinon, on recommence
avec a
= a choisi au hasard dans E.
On peut montrer qu’il y a beaucoup de a ∈ E d’ordre pair qui font l’affaire ; donc,
c’est un bon algorithme.
Rapidit´ e de l’algorithme
La seule partie de l’algorithme qui ne s’effectue pas
en temps polynomial est le calcul de l’ordre de a. C’est pour cette seule partie de
l’algorithme qu’un ordinateur quantique prend la rel` eve.
Calcul de l’ordre de a modulo n avec un ordinateur quantique Nous nous
contenterons de donner quelques id´ ees. On ´ ecrit les nombres en base 2. Si n s’´ ecrit
avec m chiffres dans {0, 1}, alors n < 2
m et donc, a < 2
m . En base 2, les entiers
k ∈ E = {1, . . . , 2
m
− 1} deviennent
k = [j m−1 j m−2 . . . j 1 j 0 ] = j m−1 2
m−1 + j m−2 2
m−2 + · · · + j 1 2
1 + j 0 2
0 .
Se donner k revient donc `
a se donner m bits j m−1 , . . . , j 0 dans {0, 1}. Pour calculer
l’ordre de a, on voudrait pouvoir calculer a
k pour tous les k simultan´ ement, c’est-` a-dire
pour tous les [j m−1 . . . j 0 ] ∈ {0, 1}
m . Essayer tous les k ∈ E, c’est essayer toutes les
possibilit´ es j i = 0 et j i = 1, pour i = 0, . . . m − 1, soit 2
m possibilit´ es. C’est l` a que
l’ordinateur quantique vient `
a la rescousse. On remplace les bits classiques j i par des
bits quantiques .
Les bits quantiques Un bit quantique a la propri´ et´ e de pouvoir se mettre dans un ´ etat
superpos´ e. Il est dans l’´ etat |0 avec probabilit´ e |α|
2 et dans l’´ etat |1 avec probabilit´ e
237
(r − 1, n) = d > 1. Puisque n ne divise pas r − 1, d est un diviseur de n diff´ erent de n.
De mˆ eme si p | r + 1.
Exemple Si n = 65 et r = 14, alors r
2 = 196 = 3 × 65 + 1 ≡ 1 (mod 65) et r − 1 = 13
est un diviseur de 65.
Par contre, si on prend s = 64 ≡ −1 (mod 65), alors s
2
≡ (−1)
2 = 1 (mod 65). On voit
que s + 1 = 65 est divisible par 65. Donc, ce s ne nous est d’aucun secours pour trouver
un diviseur propre de 65.
Comment trouver r ? On prend a au hasard dans E = {1, . . . , n − 1}.
• On commence par calculer (a, n).
• Si (a, n) = d, on a trouv´ e un diviseur de n.
• Si (a, n) = 1, on calcule les puissances de a : a, a
2 , a
3 , . . . On les r´ eduit modulo
n : a
k
≡ a k (mod n), o` u a k ∈ E.
• Comme E est fini, il existe k et l tels que a k = a l . On peut supposer k > l. Alors,
a k−l ≡ a
k−l
≡ 1 (mod n).
• Donc, il existe s minimum tel que a
s
≡ 1 (mod n). Ce nombre s est appel´ e l’ordre
de a. On a s ≤ n.
• Si s est impair, a n’´ etait pas un bon choix. On recommence avec a
= a choisi au
hasard dans E.
• Si s est pair, s = 2m. On prend r ≡ a
m (mod n), o` u r ∈ E. Alors, r
2
≡ a
2m =
a
s
≡ 1 (mod n).
• Si ni r − 1 ni r + 1 ne sont divisibles par n, on a termin´ e. Sinon, on recommence
avec a
= a choisi au hasard dans E.
On peut montrer qu’il y a beaucoup de a ∈ E d’ordre pair qui font l’affaire ; donc,
c’est un bon algorithme.
Rapidit´ e de l’algorithme
La seule partie de l’algorithme qui ne s’effectue pas
en temps polynomial est le calcul de l’ordre de a. C’est pour cette seule partie de
l’algorithme qu’un ordinateur quantique prend la rel` eve.
Calcul de l’ordre de a modulo n avec un ordinateur quantique Nous nous
contenterons de donner quelques id´ ees. On ´ ecrit les nombres en base 2. Si n s’´ ecrit
avec m chiffres dans {0, 1}, alors n < 2
m et donc, a < 2
m . En base 2, les entiers
k ∈ E = {1, . . . , 2
m
− 1} deviennent
k = [j m−1 j m−2 . . . j 1 j 0 ] = j m−1 2
m−1 + j m−2 2
m−2 + · · · + j 1 2
1 + j 0 2
0 .
Se donner k revient donc `
a se donner m bits j m−1 , . . . , j 0 dans {0, 1}. Pour calculer
l’ordre de a, on voudrait pouvoir calculer a
k pour tous les k simultan´ ement, c’est-` a-dire
pour tous les [j m−1 . . . j 0 ] ∈ {0, 1}
m . Essayer tous les k ∈ E, c’est essayer toutes les
possibilit´ es j i = 0 et j i = 1, pour i = 0, . . . m − 1, soit 2
m possibilit´ es. C’est l` a que
l’ordinateur quantique vient `
a la rescousse. On remplace les bits classiques j i par des
bits quantiques .
Les bits quantiques Un bit quantique a la propri´ et´ e de pouvoir se mettre dans un ´ etat
superpos´ e. Il est dans l’´ etat |0 avec probabilit´ e |α|
2 et dans l’´ etat |1 avec probabilit´ e