238
7 La cryptographie ` a cl´ e publique
|β|
2 , α et β ´ etant des nombres complexes tels que |α|
2 + |β|
2 = 1. En m´ ecanique
quantique, on dira que son ´ etat est α|0 + β|1. Pour nous donner une analogie, pensons
` a un sou : il a une chance sur deux de tomber pile et une chance sur deux de tomber
face. Avant le lancer, notre sou est donc dans un ´ etat superpos´ e. Par contre, quand on
le lance, on observe soit pile, soit face. C’est la mˆ eme chose pour un bit quantique. Si
on le mesure, on obtient 0 avec probabilit´ e |α|
2 et 1 avec probabilit´ e |β|
2 .
Le grand parall´ elisme d’un ordinateur quantique
Si on met tous les bits
j m−1 , . . . , j 0 dans un ´ etat superpos´ e en mˆ eme temps, alors, en calculant a
|k (mod n),
o` u |k est une superposition de tous les k ∈ E, on fait le calcul a
k pour tous les k ∈ E
simultan´ ement ! Comme le calcul quantique est lin´ eaire et r´ eversible, on peut voir
a
|k (mod n) comme une superposition de tous les a k ≡ a
k (mod n), chacun ´ etant li´ e
` a la valeur de k ∈ E associ´ ee. Toute l’information qui nous est n´ ecessaire se retrouve
maintenant dans cet ´ etat, mais on ne peut y acc´ eder sans le mesurer. La difficult´ e est
de r´ ecup´ erer le r´ esultat. Ici, cela devient de la m´ ecanique quantique, et nous n’irons pas
plus loin.
Remarque On a d´ ej` a montr´ e dans la section pr´ ec´ edente qu’il n’est pas difficile pour
un ordinateur classique de calculer a
k (mod n) . En effet, si k = j m−1 2
m−1 + · · · + j 0 2
0 ,
alors a
k =
{i|ji=1} a
2
i . Il suffit donc de calculer les a
2
i (mod n) pour i = 0, . . . , m − 1.
Ce calcul se fait de proche en proche :
• a = a 0 ;
• a
2
≡ a 1 (mod n), o` u a 1 ∈ E ;
• a
4
≡ (a 1 )
2
≡ a 2 (mod n), o` u a 2 ∈ E ;
•
. . .
• a
2
m−1 ≡ (a m−2 )
2
≡ a m−1 (mod n), o` u a m−1 ∈ E.
Finalement, a
k
≡
{i|ji=1} a i (mod n).
O` u en est l’ordinateur quantique ? Quoique l’ordinateur quantique ne pr´ esente
aucune menace ` a la cryptographie RSA pour l’instant, des montages physiques r´ eels ont
d´ ej` a permis la factorisation de tr` es petits nombres (en 2002, le nombre 15 a ´ et´ e factoris´ e
` a l’aide d’un ordinateur `
a sept bits quantiques simultan´ ement dans un ´ etat superpos´ e
par l’´ equipe d’Isaac Chuang.)
7.6 Exercices
1. Soient a, b, c, d, x, y ∈ Z. Montrer que :
a) a ≡ c (mod n) et b ≡ d (mod n)
= ⇒
a + b ≡ c + d (mod n).
b) a ≡ c (mod n) et b ≡ d (mod n)
= ⇒
ax + by ≡ cx + dy (mod n).
2. La fonction d’Euler φ : N → N est d´ efinie comme suit : si m ∈ N alors φ(m) est
le nombre d’entiers de l’ensemble {1, 2, . . . , m − 1} qui sont relativement premiers
avec m.
7 La cryptographie ` a cl´ e publique
|β|
2 , α et β ´ etant des nombres complexes tels que |α|
2 + |β|
2 = 1. En m´ ecanique
quantique, on dira que son ´ etat est α|0 + β|1. Pour nous donner une analogie, pensons
` a un sou : il a une chance sur deux de tomber pile et une chance sur deux de tomber
face. Avant le lancer, notre sou est donc dans un ´ etat superpos´ e. Par contre, quand on
le lance, on observe soit pile, soit face. C’est la mˆ eme chose pour un bit quantique. Si
on le mesure, on obtient 0 avec probabilit´ e |α|
2 et 1 avec probabilit´ e |β|
2 .
Le grand parall´ elisme d’un ordinateur quantique
Si on met tous les bits
j m−1 , . . . , j 0 dans un ´ etat superpos´ e en mˆ eme temps, alors, en calculant a
|k (mod n),
o` u |k est une superposition de tous les k ∈ E, on fait le calcul a
k pour tous les k ∈ E
simultan´ ement ! Comme le calcul quantique est lin´ eaire et r´ eversible, on peut voir
a
|k (mod n) comme une superposition de tous les a k ≡ a
k (mod n), chacun ´ etant li´ e
` a la valeur de k ∈ E associ´ ee. Toute l’information qui nous est n´ ecessaire se retrouve
maintenant dans cet ´ etat, mais on ne peut y acc´ eder sans le mesurer. La difficult´ e est
de r´ ecup´ erer le r´ esultat. Ici, cela devient de la m´ ecanique quantique, et nous n’irons pas
plus loin.
Remarque On a d´ ej` a montr´ e dans la section pr´ ec´ edente qu’il n’est pas difficile pour
un ordinateur classique de calculer a
k (mod n) . En effet, si k = j m−1 2
m−1 + · · · + j 0 2
0 ,
alors a
k =
{i|ji=1} a
2
i . Il suffit donc de calculer les a
2
i (mod n) pour i = 0, . . . , m − 1.
Ce calcul se fait de proche en proche :
• a = a 0 ;
• a
2
≡ a 1 (mod n), o` u a 1 ∈ E ;
• a
4
≡ (a 1 )
2
≡ a 2 (mod n), o` u a 2 ∈ E ;
•
. . .
• a
2
m−1 ≡ (a m−2 )
2
≡ a m−1 (mod n), o` u a m−1 ∈ E.
Finalement, a
k
≡
{i|ji=1} a i (mod n).
O` u en est l’ordinateur quantique ? Quoique l’ordinateur quantique ne pr´ esente
aucune menace ` a la cryptographie RSA pour l’instant, des montages physiques r´ eels ont
d´ ej` a permis la factorisation de tr` es petits nombres (en 2002, le nombre 15 a ´ et´ e factoris´ e
` a l’aide d’un ordinateur `
a sept bits quantiques simultan´ ement dans un ´ etat superpos´ e
par l’´ equipe d’Isaac Chuang.)
7.6 Exercices
1. Soient a, b, c, d, x, y ∈ Z. Montrer que :
a) a ≡ c (mod n) et b ≡ d (mod n)
= ⇒
a + b ≡ c + d (mod n).
b) a ≡ c (mod n) et b ≡ d (mod n)
= ⇒
ax + by ≡ cx + dy (mod n).
2. La fonction d’Euler φ : N → N est d´ efinie comme suit : si m ∈ N alors φ(m) est
le nombre d’entiers de l’ensemble {1, 2, . . . , m − 1} qui sont relativement premiers
avec m.