Compléments d’arithmétique

Vidéo ■ partie 14.1. Fractions continues

Vidéo ■ partie 14.2. Algorithme de Shor pour n'importe quel ordre
Vidéo ■ partie 14.3. L'algorithme de Shor fonctionne au moins une fois sur deux
Nous apportons des compléments à l’algorithme de Shor vu lors du chapitre précédent en étudiant
chacune des hypothèses.

Dans ce chapitre il n’y a pas d’informatique quantique mais beaucoup de mathématiques ! Certaines
parties sont assez techniques et d’un niveau un peu plus élevé que les chapitres précédents.

1. Fractions continues

1.1. Motivation
Dans le chapitre précédent nous avons fait une hypothèse simplificatrice : l’ordre r divise 2n . Ce n’est pas
vrai en général, mais l’algorithme de Shor reste valide moyennant quelques adaptations.
Reprenons la fin du circuit de l’algorithme de Shor qui permet de calculer l’ordre r d’un élément.
m
• Si r divise 2n alors la mesure du premier registre conduit à un nombre rationnel x = 2n qui est aussi
égal à ℓr . Ainsi x est un multiple de 1r et permet de retrouver r (ou au moins un facteur de r).
m
• Si r ne divise pas 2n alors la mesure du premier registre conduit à un nombre rationnel x = 2n qui est
proche d’un multiple de 1r (mais n’est pas exactement un multiple). Comment retrouver r à partir de x ?
Voici l’exemple que l’on étudiera en détails dans la section suivante afin de factoriser N = 21 à l’aide du
choix a = 2. Imaginons qu’une mesure conduise à x = 427 512 . Comment retrouver l’ordre r ? On pourrait aussi
obtenir x = 512 ou bien x = 512 . On voit que x est proche de 45 . Mais est-ce que 5 est vraiment la période ?
426 428

1.2. Fractions continues

Une fraction continue est une fraction
1
a0 + 1
a1 + 1
a2 +
···+ a1
n
où a0 ⩾ 0 et ai > 0 (pour i > 0). On note cette fraction par la liste [a0 , a1 , . . . , an ].
p
On note qnn l’écriture irréductible du rationnel [a0 , a1 , . . . , an ].

Exemple.
L’écriture en fraction continue [5, 2, 1, 4] représente le nombre rationnel :
1 75
x =5+ 1
= = 5.3571428 . . .
2+ 1 14
1+ 4
COMPLÉMENTS D’ARITHMÉTIQUE 2

Prendre les sous-listes de la fraction continue permet d’obtenir des approximations de x de plus en plus
précises :
p
• Sous liste [5], alors q00 = 5.
p 11
• Sous liste [5, 2] alors q11 = 2 = 5.5.
p 16
• Sous liste [5, 2, 1] alors q22 = 3 = 5.33 . . .
p3 75
• Liste complète [5, 2, 1, 4] alors q3 = 14 = x.

1.3. Approximations par les fractions continues

Les fractions continues prennent tout leur intérêt pour approcher des réels (ou des rationnels) par des
fractions simples. Prenons l’exemple de π. Comment approcher π par une fraction avec un dénominateur
pas trop grand (disons avec moins de trois chiffres) ? L’idée la plus simple est d’utiliser l’écriture décimale
π = 3.1415 . . . ≃ 314
100 . Mais peut-on faire mieux ?
Calculons pour commencer la fraction continue de x = 314 100 . Cela se fait par des divisions euclidiennes
successives : 314 = 3 × 100 + 14 donc
314 14 1
=3+ = 3 + 100 ,
100 100 14
puis 100 = 7 × 14 + 2, donc
314 1 1
=3+ 2
=3+ .
100 7 + 14 7 + 17
Ainsi
314 1 22
≃3+ =
100 7 7
Nous avons donc approché π par 22 7 = 3.1428 . . . ce qui est aussi bien que 314
100 mais avec un dénominateur
beaucoup plus petit.
314 159
Bien évidemment on peut pousser les calculs plus loin : π ≃ 100 000 . On calcule la fraction continue de π
314 159
(ou de 100 000 ) et on obtient [3, 7, 15, 1, . . .]. Cela fournit les approximations successives :
p 22
• Sous liste [3, 7], alors q11 = 7 = 3.1428 . . .
p 333
• Sous liste [3, 7, 15], alors q22 = 106 = 3.141509 . . .
p 355
• Sous liste [3, 7, 15, 1], alors q33 = 113 = 3.14159292 . . .
Ainsi avec des fractions dont les dénominateurs restent petits, on trouve de très bonnes approximations de
π. En un sens les fractions continues donnent les meilleures approximations possibles d’un réel x par des
rationnels.

1.4. Exemple
Reprenons l’exemple de la factorisation de N = 21 à l’aide du choix a = 2. Supposons que le circuit de Shor
427
nous donne la valeur x = 512 , comment obtenir l’ordre r ?
La mauvaise idée est d’utiliser l’écriture décimale pour dire x = 427 400 4
512 ≃ 500 = 5 donc le dénominateur naturel
(qui donne l’ordre r) serait 5. Ce n’est pas vrai.
La bonne méthode est de calculer le développement en fraction continue de x :
427 1
x= = [0, 1, 5, 42, 2] = 0 +
512 1 + 11
5+
42+ 1
2

Ce qui fournit les approximations successives :

1 p 1
• Sous liste [0, 1] = 0 + 1 , alors q11 = 1 = 1.
1
• Sous liste [0, 1, 5] = 0 + = 65 .
1+ 15
COMPLÉMENTS D’ARITHMÉTIQUE 3

1 211
• Sous liste [0, 1, 5, 42] = 0 + 1+ 1 = 253 .
1
5+ 42
427
• Sous liste [0, 1, 5, 42, 2] = 512 .
Les dénominateurs sont les candidats pour l’ordre r, mais on sait que l’ordre r cherché est inférieur à l’entier
N = 21. Donc ici, la meilleure fraction ayant un dénominateur inférieur à N est 56 , on trouve ainsi r = 6. Il
est facile de vérifier que l’ordre de a = 2 modulo N = 21 est bien r = 6.
Lors de la mesure on peut aussi obtenir des valeurs légèrement différentes par exemple x ′ = 426 512 ou bien
′′ 428
x = 512 . Que se passe-t-il alors ?
426 1 4 5 104 213
• Si x ′ = 512 = [0, 1, 4, 1, 20, 2], les fractions successives sont 1 , 5 , 6 , 125 , 256 . La meilleure fraction ayant
5
un dénominateur inférieur à N est 6 , on retrouve ainsi r = 6.
428 1 5 51 107
• Si x ′′ = 512 = [0, 1, 5, 10, 2], les fractions successives sont 1 , 6 , 61 , 128 . La meilleure fraction ayant un
dénominateur inférieur à N est encore 56 et on retrouve r = 6.
Conclusion : la méthode des fractions continues permet de retrouver l’ordre r.

2. Algorithme de Shor pour n’importe quel ordre pair

2.1. Fin du circuit

• Cas du chapitre précédent. Si r divise 2n alors la mesure du premier registre conduit à la mesure d’un
état 2r ℓ et donne donc un entier m = 2r ℓ . On définit alors le rationnel x = 2mn qui est aussi égal à ℓr
n n

et qui permet de retrouver r (ou au moins un facteur de r). Noter que comme r divise 2n , m est un
n
multiple de 2r . Autrement dit, x est un multiple (avec un facteur entier) de 1r .
• Cas considéré maintenant. Si r ne divise pas 2n alors la mesure du premier registre conduit à un entier
m. Cet entier m est proche de 2r ℓ (pour un certain entier ℓ) mais la fraction 2r ℓ n’est plus un entier.
n n

Autrement dit on obtient un nombre rationnel x = 2mn qui est proche d’un multiple de 1r (mais n’est pas
exactement un multiple).

2.2. L’exemple N = 21 : début

Soit N l’entier à factoriser. Dans toute la suite on considérera l’exemple de N = 21. Dans le cas où r divise 2n ,
il suffisait de choisir l’entier n tel que N ⩽ 2n . Dans le cas général on choisit n de sorte à avoir les inégalités
N 2 ⩽ 2n < 2N 2 . Pour N = 21, on a N 2 = 441, donc avec n = 9 on a bien N 2 ⩽ 2n = 512 < 2N 2 .
Reprenons les calculs du circuit de Shor :
• Initialisation.
|ψ0 〉 = |0〉⊗n ⊗ |0〉⊗n .
• Transformation de Hadamard.

2n −1
‚ Œ
1 X
|ψ1 〉 = p k ⊗ 0 .
2n k=0
• Oracle.
2n −1
1 X
|ψ2 〉 = p k ⊗ ak .
n
2 k=0

2.3. L’exemple N = 21 : milieu

Choisissons ensuite un entier a inversible modulo N . Prenons simplement a = 2 qui est bien premier avec
N = 21. Nous devons retrouver l’ordre de a modulo N qui est ici r = 6.
Réordonnons les éléments de |ψ2 〉 en regroupant les termes selon le second facteur qui est l’un des a k
pour k variant de 0 à r − 1 = 5.
COMPLÉMENTS D’ARITHMÉTIQUE 4

€ Š
1
|ψ2 〉 = p512 0 + 6 + · · · + 504 + 510 1
€ Š
p1 1 + 7 + · · · + 505 + 511 2
512
€ Š
p1 2 + 8 + · · · + 506 4
512
€ Š
p1 3 + 9 + · · · + 507 8
512
€ Š
p1 4 + 10 + · · · + 508 16
512
€ Š
p1 5 + 11 + · · · + 509 11
512

Bien noter la différence avec le cas où r était une puissance de 2. Ici on n’obtient pas un tableau rectangulaire.
Les deux premières lignes contiennent une somme de 86 termes alors que les suivantes en ont seulement
85.
On effectue ensuite une mesure du second registre et on obtient l’un des a k . Dans la suite on suppose par
exemple qu’on obtient 2 , alors le premier registre, une fois normalisé, contient le qubit :
€ Š
ψ̄3 = p186 1 + 7 + 13 + · · · + 505 + 511 .

2.4. L’exemple N = 21 : fin

La dernière étape est d’appliquer la transformée de Fourier inverse et d’effectuer une mesure sur le premier
registre.

ψ̄4 = F̂ −1 ψ̄3
85
‚ Œ
X
= F̂ −1 p1 6α + 1
86
α=0
85 511
(6α+1) j
X X ¶
= p1 p1 e −2iπ 512
j
86 512
α=0 j=0
511 85
‚ Œ
6α j j
X X ¶
= p1 p1 e −2iπ 512
e−2iπ 512 j
512 86
j=0 α=0

Cette fois la somme

85
6α j
X
Σ( j) = p1 e−2iπ 512
86
α=0
est un nombre complexe qui peut prendre des valeurs autres que 0 et 1.
La mesure du premier registre conduit à la valeur j avec la probabilité :
1 2
pj = 512 |Σ( j)| .
2n ℓ
Ces probabilités sont presque nulles sauf pour les valeurs de j proches des réels r (qui ne sont pas des
entiers) avec ℓ = 0, 1, . . . , r − 1. Nous avons ici
2n 512
= = 85.33 . . .
r 6
2n ℓ
Les valeurs r pour ℓ = 0, . . . , 5 sont les réels :
0 85.33 . . . 170.66 . . . 256 341.33 . . . 426.66 . . .
COMPLÉMENTS D’ARITHMÉTIQUE 5

Donc ici les probabilités sont presque nulles, sauf autour de entiers :
j = 0, j = 85, j = 171, j = 256, j = 341, j = 427.
Voici le diagramme des probabilités p j , pour 0 ⩽ j < 512. Les 6 pics sont nettement visibles.

Voici le tableau des valeurs autour du pic à j = 427.

j pj
422 0.00062 . . .
423 0.00099 . . .
424 0.00186 . . .
425 0.00469 . . .
426 0.02888 . . .
427 0.11389 . . .
428 0.00702 . . .
429 0.00226 . . .
430 0.00109 . . .
431 0.00063 . . .
On note la probabilité élevée en j = 427, une probabilité plus faible en j = 426 (qui s’explique car pour
ℓ = 5, 2r ℓ = 512×5
n
6 = 426.66 . . .), pour les valeurs plus éloignées les probabilités sont presque nulles.

2.5. Ordre
On obtient l’ordre r, ou l’un de ses facteurs, à partir du développement en fractions continues comme
expliqué précédemment. À part cela, les conclusions sont similaires aux cas du chapitre « Algorithme de
Shor » :
• Si la mesure donne un entier j proche de 0, alors on n’obtient aucune information sur l’ordre r, il faut
recommencer.
• Si la mesure donne un entier j proche de 85 ou proche de 427, alors le développement en fraction
j
continue de 512 donne l’ordre r = 6.
COMPLÉMENTS D’ARITHMÉTIQUE 6

• Si la mesure donne un entier proche j proche de 171 ou 341 alors on n’obtient pas r mais le facteur
r ′ = 3 ; si la mesure donne un entier j proche de 256 alors on n’obtient pas r mais le facteur r ′′ = 2.
Dans ces cas on relance l’algorithme pour obtenir la factorisation complète.

2.6. Conclusion
Il nous reste à justifier que l’approximation du pic conduit au bon résultat.
Théorème 1 (Hardy – Wright).
p
Soit x ∈ R. Soit une fraction q telle que :
p 1
x− < 2.
q 2q
p
Alors q est obtenu comme l’une des fractions du développement en fractions continues de x.
2n ℓ 2n ℓ
Dans notre situation nous considérons l’entier m le plus proche de r . Donc m − r ⩽ 21 . En posant x = 2mn
on obtient x − ℓr ⩽ 2n+1
1
. Par notre choix de n on a 2n ⩾ N 2 > r , donc x −
2 ℓ 1
r ⩽ 2r 2 . Par le théorème,
ℓ
r s’obtient comme l’une des fractions du développement en fractions continues de x, comme on l’avait
expliqué dans la première section.

Le reste du chapitre est consacré à la théorie des groupes afin de justifier la pertinence des hypothèses 1 et 2 de
l’algorithme de Shor.

3. Ordre d’un élément

3.1. Définition
Soit (G, ×) un groupe commutatif ayant pour élément neutre e. L’ordre de x ∈ G, noté ord(x), est le plus
petit entier r > 0, tel que x r = e.
Voici quelques propriétés de l’ordre :
• si k est un entier tel que x k = e alors ord(x) divise k ;
• ord(x k ) divise ord(x).
Le théorème de Lagrange pour un groupe fini G de cardinal n affirme que x n = e quel que soit x. Ainsi
ord(x) divise n, quel que soit l’élément x. En particulier, tout élément admet un ordre fini.

3.2. Plus grand ordre

Proposition 1.
Soit G un groupe fini et m le plus grand ordre parmi tous les x ∈ G, alors pour tout x ∈ G, ord(x) divise m.
Une formulation équivalente est la suivante : soit ℓ le plus petit entier tel que pour tout x ∈ G on ait x ℓ = e,
alors il existe x 0 ∈ G tel que ord(x 0 ) = ℓ.
Pour la preuve nous aurons besoin du résultat suivant :
Lemme 1.
Soient deux éléments x et y d’ordres m = ord(x) et n = ord( y) premiers entre eux, alors ord(x · y) = mn.

Démonstration. Notons r = ord(x y). Il s’agit de montrer r = mn en prouvant que r|mn puis que mn|r.
Tout d’abord (x y)mn = x mn · y mn = (x m )n · ( y n )m = e, donc r|mn. Réciproquement, on sait que (x y) r = e
donc x r · y r = e, autrement dit z = x r = y −r . D’une part z m = (x r )m = x r m = (x m ) r = e, donc ord(z)|m, de
même z n = ( y r )n = e, donc ord(z)|n. Comme m et n sont premiers entre eux, alors ord(z) = 1, c’est-à-dire
z = e. Ainsi x r = e, donc m = ord(x)|r et y r = e donc n = ord( y)|r, ainsi mn|r.
COMPLÉMENTS D’ARITHMÉTIQUE 7

Preuve de la proposition. Soit m le plus grand ordre parmi les éléments de G, il existe donc y d’ordre m.
Fixons x un élément quelconque de G et notons n son ordre. Il s’agit de montrer que n|m. Par l’absurde
on suppose que n ne divise pas m. On va obtenir une contradiction en construisant un élément z avec
ord(z) > m. Par exemple si m et n sont premiers entre eux, alors z = x y est d’ordre mn > m, ce qui donne
la contradiction. Si m et n ne sont pas premiers entre eux, soit p un facteur premier commun à m et n tel
f
que p e |n, p f |m avec e > f les plus grands possibles (un tel p existe car n ne divise pas m). Soient y ′ = y p
e
et x ′ = x n/p . Alors y ′ a pour ordre m′ = m/p f et x ′ a pour ordre n′ = p e . Les entiers m′ et n′ sont premiers
entre eux (car m′ n’est pas divisible par p). Ainsi z = x ′ y ′ a pour ordre m′ n′ = pmf p e = mp e− f > m. On
obtient bien la contradiction cherchée.

4. Le groupe (Z/pZ)∗
Dans toute la suite nous allons étudier en détails le groupe (Z/nZ)∗ qui est l’ensemble des éléments
inversibles modulo n. Nous commençons par le cas d’un nombre premier p. Nous savons déjà que
Card(Z/pZ)∗ = ϕ(p) = p − 1
mais nous souhaitons aller plus loin en étudiant la structure de (Z/pZ)∗ .

4.1. Isomorphisme
Théorème 2.
Le groupe (Z/pZ)∗ , × est isomorphe au groupe Z/(p − 1)Z, + .

Pour la preuve nous aurons besoin du résultat suivant.

Proposition 2.
Un polynôme P ∈ Z/pZ[X ] de degré d possède au plus d racines, c’est-à-dire des éléments x ∈ Z/pZ tels que
P(x) ≡ 0 (mod p).

Idée de la preuve de la proposition. C’est un fait général : sur un corps k un polynôme P ∈ k[X ] de degré
d a au plus d racines. En effet, a ∈ k est une racine si et seulement si X − a est un facteur de P(X ). Si
{a1 , . . . , ak } est l’ensemble des racines de P(X ) alors (X − a1 )(X − a2 ) · · · (X − ak ) divise P(X ) et donc en
comparant les degrés : deg P ⩾ k.

Preuve du théorème. L’ensemble (Z/pZ)∗ = {1, 2, . . . , p−1} est en bijection avec Z/(p−1)Z = {0, 1 . . . , p−2}.
Mais on veut plus : on veut que les structures de groupes, avec la loi « × » pour (Z/pZ)∗ et « + » pour
Z/(p − 1)Z, soient préservées. Nous allons trouver un élément a d’ordre p − 1 dans (Z/pZ)∗ ce qui va nous
permettre de construire l’isomorphisme :
φ : Z/(p − 1)Z −→ (Z/pZ)∗
k 7−→ a k (mod p).
Cette application φ est bien définie car φ(k + ℓ(p − 1)) = a k+ℓ(p−1) = a k = φ(k) et est un morphisme car
φ(k + k′ ) = φ(k) × φ(k′ ). De plus φ est bijective, car elle est surjective (puisque les {a k } sont p − 1 éléments
distincts, ils forment l’ensemble d’arrivée) et les ensembles de départ et d’arrivée ont le même nombre
d’éléments.
Pour montrer qu’il existe un élément d’ordre p − 1, remarquons d’abord que pour tout élément x ∈ (Z/pZ)∗
on a ord(x)|p − 1. En effet, par le petit théorème de Fermat, x p−1 ≡ 1 (mod p). Soit m le plus grand des
ordres des éléments de (Z/pZ)∗ . On vient de voir que m|p − 1, donc m ⩽ p − 1. Par la proposition 1, on sait
que pour tout x ∈ (Z/pZ)∗ , ord(x) divise m, c’est-à-dire x m ≡ 1 (mod p). Considérons le polynôme défini
par P(X ) = X m − 1. Alors pour tout x ∈ (Z/pZ)∗ , P(x) = x m − 1 ≡ 0 (mod p). Nous avons donc trouvé
p − 1 racines au polynôme P de degré m, donc p − 1 ⩽ m. Conclusion : m = p − 1, donc par définition de m
il existe un élément a d’ordre p − 1.
COMPLÉMENTS D’ARITHMÉTIQUE 8

Remarque : la preuve n’est pas constructive, pour trouver a d’ordre p − 1 il n’y a pas d’autres moyens que
de tester différentes valeurs de a et de calculer à chaque fois a, a2 , a3 , . . .

4.2. Éléments d’ordre pair

Proposition 3.
Dans (Z/pZ)∗ , avec p ⩾ 3, la moitié au moins des éléments sont d’ordre pair.

Démonstration. Notons ψ : (Z/pZ)∗ → Z/(p − 1)Z l’isomorphisme de groupes. Alors l’ordre d’un élément
x de (Z/pZ)∗ est égal à l’ordre de l’élément ψ(x) dans Z/(p − 1)Z.
L’ordre d’un élément y dans le groupe additif Z/(p − 1)Z est le plus petit entier r > 0 tel que r · y ≡ 0
p−1
(mod p − 1). Considérons les entiers impairs y = 2k + 1, k = 0, 1, . . . , 2 . Ces y ont des ordres pairs : en
effet si r · (2k + 1) ≡ 0 (mod p − 1) alors r(2k + 1) = ℓ(p − 1). Comme ℓ(p − 1) est pair (car p est premier
et supérieur à 3) et que 2k + 1 est impair, r est nécessairement pair. Ainsi la moitié au moins des éléments
de Z/(p − 1)Z sont d’ordre pair. Par isomorphie, il en est de même pour (Z/pZ)∗ .

4.3. Racines carrées de 1

Le point-clé initial de l’algorithme de Shor est la factorisation x 2 − 1 = (x − 1)(x + 1). Dans (Z/nZ)∗ trouver
un élément tel que x 2 − 1 = 0 peut permettre une factorisation de n à l’aide de (x − 1)(x + 1).
Définition.
On appelle racine carrée de 1 modulo n tout élément x de Z/nZ tel que

x 2 ≡ 1 (mod n)

Une telle racine carrée est en fait nécessairement un élément de (Z/nZ)∗ . Attention ! L’équation X 2 − 1 = 0
est une équation polynomiale de degré 2. Elle peut avoir plus de deux solutions dans (Z/nZ)∗ qui n’est pas
toujours un corps, nous y reviendrons. Revenons au cas où n = p est un nombre premier, pour lequel Z/pZ
est un corps. Il y a dans ce cas effectivement deux solutions.
Proposition 4.
Il y a exactement deux racines carrées modulo p (où p ⩾ 3 est un nombre premier) : +1 et −1.
Encore une fois, ceci n’est valable que modulo un nombre premier.
Après l’application de l’isomorphisme ψ : (Z/pZ)∗ → Z/(p − 1)Z, les deux racines carrées sont ψ(1) = 0 et
p−1 p−1
ψ(−1) = 2 (en effet l’identité (−1)2 ≡ 1 (mod p) devient 2 × 2 ≡ 0 (mod p − 1)).

Démonstration. Pour x = +1 on a bien sûr x 2 = 1. L’écriture x = −1 est une autre façon d’écrire x = p − 1
(car x = p − 1 ≡ −1 (mod p)) et bien sûr x 2 = (−1)2 = 1.
Pour justifier qu’il n’y a pas d’autres racines : si x est une racine carrée de 1 alors x 2 − 1 ≡ 0 (mod p) donc
(x − 1)(x + 1) ≡ 0 (mod p). Comme Z/pZ est un corps, un produit est nul si et seulement si un des facteur
est nul, donc x − 1 ≡ 0 (mod p) ou x + 1 ≡ 0 (mod p), c’est-à-dire x = +1 ou x = −1 (modulo p).
Un autre argument serait de dire que +1 et −1 sont racines du polynôme P(X ) = X 2 − 1, et comme
deg P(X ) = 2, il n’y a pas d’autres solutions par la proposition 2.

Cependant le point clé de l’algorithme de Shor est un peu plus délicat, il s’agit de trouver un entier r pair
tel que x r ≡ 1 (mod n), ce qui donne la factorisation (x r/2 − 1)(x r/2 + 1) ≡ 0 (mod n) et peut conduire
à une factorisation de n à partir de la factorisation (x r/2 − 1)(x r/2 + 1). Il faut supposer que x r/2 + 1 ̸≡ 0
(mod n) pour que la procédure fonctionne, voir l’hypothèse 2 du chapitre « Algorithme de Shor ».
Faisons le point : pour l’algorithme de Shor, on cherche un entier pair r tel que x r/2 soit une racine carrée
de 1, en excluant le cas où x r/2 ≡ 1 (mod n) (pour lequel l’ordre serait r/2 et pas r) et x r/2 ≡ −1 (mod n)
(qui ne permet pas toujours d’obtenir une factorisation).
COMPLÉMENTS D’ARITHMÉTIQUE 9

Dans le cas d’un nombre premier : une telle racine carrée n’existe pas, car on a vu que les deux seules
racines carrées de 1 sont +1 et −1 qui sont justement les deux cas à éviter.
Ainsi :
Proposition 5.
Lorsque p est un nombre premier, l’hypothèse 1 ou l’hypothèse 2 de l’algorithme de Shor n’est pas vérifiée.
Noter que ce résultat négatif n’a pas d’incidence pour l’algorithme de Shor pour lequel il s’agit de factoriser
un entier qui n’est pas premier. Nous avons déjà expliqué pourquoi cette proposition est vraie, nous le
justifions de nouveau de manière plus condensée.

Démonstration. Soit x ∈ (Z/pZ)∗ . Supposons que l’hypothèse 1 soit vraie, c’est-à-dire que l’ordre r de x
est pair. Comme x r − 1 ≡ 0 (mod p) alors (x r/2 − 1)(x r/2 + 1) ≡ 0 (mod p). Mais x r/2 − 1 ̸≡ 0 (mod p)
car sinon l’ordre serait ⩽ r/2. Comme p est un nombre premier alors x r/2 − 1 ̸≡ 0 est inversible. Si y
désigne son inverse, alors en multipliant par cet inverse on obtient y(x r/2 − 1)(x r/2 + 1) ≡ 0 (mod p), donc
x r/2 + 1 ≡ 0 (mod p) et ainsi x r/2 ≡ −1 (mod p) ce qui empêche l’hypothèse 2 d’être valide.

5. Le groupe (Z/pα Z)∗

L’étape suivante est d’étudier le groupe des éléments inversibles modulo une puissance d’un nombre premier.

5.1. Isomorphisme
€ Š
On sait déjà que Card(Z/pα Z)∗ = ϕ(pα ) = pα − pα−1 = pα 1 − 1p , mais nous allons aller plus loin en
montrant que (Z/pα Z)∗ est un groupe cyclique (pour p ⩾ 3), c’est-à-dire qu’il peut être engendré par un
seul élément.

5.2. Isomorphisme
Théorème 3.
Si p ⩾ 3 est un nombre premier alors le groupe (Z/pα Z)∗ est isomorphe au groupe Z/(p − 1)Z × Z/pα−1 Z et
c’est un groupe cyclique. Pour p = 2, (Z/2α Z)∗ est isomorphe au groupe Z/2Z × Z/2α−2 Z.

Démonstration. Nous nous limitons à p ⩾ 3, situation de l’algorithme de Shor. Nous allons construire dans
(Z/pα Z)∗ un élément a d’ordre p − 1 et un élément b d’ordre pα−1 ce qui conduira à l’isomorphisme :
φ : Z/(p − 1)Z × Z/pα−1 Z −→ (Z/pα Z)∗
(k, ℓ) 7−→ a k bℓ (mod pα ).
Tout d’abord soit a′ un élément d’ordre p − 1 dans (Z/pZ)∗ (un tel élément existe par le théorème 2), donc
a′p−1 ≡ 1 (mod p). Considérons a′ comme élément de (Z/pα Z)∗ , et notons r = ord(a′ ) de sorte que a′r ≡ 1
(mod pα ). Ainsi a′r − 1 est divisible par pα , donc a fortiori par p, donc a′r ≡ 1 (mod p). Ainsi l’ordre de a′
r
dans (Z/pZ)∗ divise r : c’est-à-dire p − 1|r. Notons a = a′ p−1 . C’est un élément d’ordre p − 1 dans (Z/pα Z)∗ :
en effet a p−1 = a′r ≡ 1 (mod pα ) et par définition de l’ordre r, il ne peut exister d’entier plus petit.
α−1 α−1
Notons b = 1 + p alors par le lemme ci-dessous b p = (1 + p) p ≡ 1 (mod pα ), donc en particulier, l’ordre
de b divise pα−1 , mais toujours par ce lemme, pour k < α − 1, b p ̸≡ 1 (mod pα ). Ainsi ord(b) = pα−1 .
k−1

Nous avons donc trouvé a avec ord(a) = p − 1 et b avec ord(b) = pα−1 . Ces deux ordres sont premiers entre
eux (car p − 1 et p le sont) donc par le lemme 1, l’élément a b est d’ordre (p − 1)pα−1 .
On a donc montré en plus que (Z/pα Z)∗ est engendré par le seul élément a b, c’est donc un groupe
cyclique.

Voici l’énoncé du lemme utilisé dans la preuve.

COMPLÉMENTS D’ARITHMÉTIQUE 10

Lemme 2.
Soient k ⩾ 0 et p ⩾ 3 un nombre premier, alors :
k
(1 + p) p ≡ 1 + p k+1 (mod p k+2 ).
La preuve de ce lemme peut être omise en première lecture. Elle se fait par récurrence sur k et reste assez
technique. C’est une version améliorée de l’exercice classique suivant : (x + y) p ≡ x p + y p (mod p). Les
ingrédients sont les mêmes dans la preuve qui nous concerne : il faut utiliser la formule du binôme de
p


Newton et utiliser que le coefficient i est divisible par p, lorsque 0 < i < p.
Nous aurons besoin pour la preuve de la variante suivante : si x ≡ y (mod p k ) avec k ⩾ 1, alors x p ≡ y p
(mod p k+1 ). Il suffit d’écrire x = y + λp k puis d’utiliser la formule du binôme de Newton, x p = ( y + λp k ) p =
p


y p + · · · où les termes de la somme omis sont tous divisibles par p k+1 (car de nouveau i est divisible par
p).

Preuve du lemme. La démonstration se fait par récurrence. Pour k = 0, l’assertion est vraie : (1 + p)1 ≡ 1 + p
(mod p2 ). Supposons l’assertion vraie au rang k ⩾ 0 et prouvons-la au rang k+1. Par hypothèse de récurrence
k
(1 + p) p ≡ 1 + p k+1 (mod p k+2 ),
donc par la variante rappelée ci-dessus :
k p
p
k+1
€ Š
(1 + p) p = (1 + p) p ≡ 1 + p k+1 (mod p k+3 ).

p
Développons 1 + p k+1 selon la formule du binôme de Newton :

p
1 + p k+1 = 1 + p · p k+1 + · · ·

p
Les termes omis dans les points de suspension sont tous divisibles par p k+3 donc 1 + p k+1 ≡ 1 + p k+2
(mod p k+3 ), ce qui conduit au résultat souhaité.

5.3. Éléments d’ordre pair

Proposition 6.
Dans (Z/pα Z)∗ , avec p ⩾ 3, la moitié au moins des éléments sont d’ordre pair.

Démonstration. Le preuve est similaire à celle de la proposition 3. L’ordre de (2k + 1, ℓ) est pair dans
Z/(p − 1)Z × Z/pα−1 Z, quel que soit l’entier impair 2k + 1 et quel que soit ℓ. Donc la moitié au moins des
éléments de Z/(p − 1)Z × Z/pα−1 Z sont d’ordre pair. Par l’isomorphisme du théorème 3, il en est de même
pour (Z/pα Z)∗ .

5.4. Racines carrées de 1

On rappelle qu’une racine carrée de 1 modulo pα est un élément x tel que x 2 ≡ 1 (mod pα ).
Proposition 7.
Il y a exactement deux racines carrées modulo pα (où p ⩾ 3 est un nombre premier) : +1 et −1.
Attention cette fois Z/pα Z n’est pas un corps, il pourrait donc y avoir à priori plus de deux racines carrées
de 1. Par l’isomorphisme, dans Z/(p − 1)Z × Z/pα−1 Z ces deux racines carrées sont (1, 0) et ( 2 , 0).
p−1

Démonstration. Notons ψ : (Z/pα Z)∗ → Z/(p − 1)Z × Z/pα−1 Z l’isomorphisme de groupes du théorème 3.
Si ψ(x) = (a, b) alors ψ(x k ) = (ka, k b) et ψ(1) = (0, 0) (l’élément neutre du groupe multiplicatif s’envoie
sur l’élément neutre du groupe additif). Donc x 2 ≡ 1 (mod pα ) équivaut à (2a, 2b) ≡ (0, 0), où plus
précisément 2a ≡ 0 (mod p − 1) et 2b ≡ 0 (mod pα−1 ). Comme pgcd(2, p) = 1 alors 2 est inversible modulo
pα−1 la seconde équation donne donc b ≡ 0 (mod pα−1 ). En revanche, comme p − 1 est pair, l’équation
p−1
2a ≡ 0 (mod p − 1) admet deux solutions a = 0 et a = 2 .
p−1
Bilan : nous avons obtenu deux solutions (0, 0) et ( 2 , 0) qui par l’isomorphisme donnent les deux seules
racines carrées 1 et −1.
COMPLÉMENTS D’ARITHMÉTIQUE 11

Nous n’allons pas étudier l’équation x r/2 +1 ≡ 0 (mod pα ), d’une part le cas n = pα est étudié spécifiquement
dans l’algorithme de Shor, d’autre part on étudiera plus tard cette équation dans le cas plus général d’un n
quelconque.

6. Le théorème des restes chinois

6.1. Cas simple

Théorème 4.
Soient p et q deux nombres premiers entre eux alors Z/pqZ est isomorphe à Z/pZ × Z/qZ.
Par exemple Z/6Z est isomorphe à Z/2Z × Z/3Z. Attention ! Z/4Z n’est pas isomorphe à Z/2Z × Z/2Z.

Démonstration. Notons φ : Z/pqZ → Z/pZ × Z/qZ, l’application définie par

φ(x) = (x, x̃)
où x est la réduction de x modulo p, et x̃ est la réduction de x modulo q.
Cette application φ est bien définie et c’est un morphisme de groupes. De plus elle est injective : si
φ(x) = (0, 0) alors x ≡ 0 (mod p) et x ≡ 0 (mod q), donc p divise x et q divise x ; ainsi p et q étant
premiers entre eux, le produit pq divise x, donc x ≡ 0 (mod pq). Comme les ensembles de départ et
d’arrivée ont le même cardinal pq alors φ est bijective.

Corollaire 1.
Soient p et q deux nombres premiers entre eux. Soient a, b ∈ Z. Il existe x ∈ Z tel que :
x ≡ a (mod p)

.
x ≡ b (mod q)

6.2. Version générale

Théorème 5.
α α α
Soit p1 1 × p2 2 × · · · × pℓ ℓ la décomposition d’un entier n en produit de facteurs premiers. Alors Z/nZ est
isomorphe au groupe Z/pα1 Z × · · · × Z/pαℓ Z.
La preuve est une récurrence à partir du cas pq.

7. Le groupe (Z/nZ)∗

7.1. Groupe produit

Si A et B sont deux groupes, alors le groupe produit A × B est défini par la loi (a, b) × (a′ , b′ ) = (aa′ , b b′ )
et l’élément neutre est (eA, eB ) formé à partir des éléments neutres de chaque groupe. En particulier
(a, b)k = (a k , b k ) et (a, b)−1 = (a−1 , b−1 ). L’ordre de (a, b) est le plus petit multiple commun des ordres de
a et b :
ord(a, b) = ppcm(ord(a), ord(b)).

7.2. Isomorphisme
COMPLÉMENTS D’ARITHMÉTIQUE 12

Proposition 8.
Soient p et q deux nombres premiers entre eux alors (Z/pqZ)∗ est isomorphe à (Z/pZ)∗ × (Z/qZ)∗ .

Démonstration. C’est le théorème des restes chinois (cas pq) avec le fait que x est premier avec pq si et
seulement si x est premier avec p et avec q.

La version générale est la suivante :

Théorème 6.
α α α
Soit p1 1 × p2 2 × · · · × pℓ ℓ la décomposition d’un entier n en produit de facteurs premiers. Alors (Z/nZ)∗ est
isomorphe au groupe (Z/pα1 Z)∗ × · · · × (Z/pαℓ Z)∗ .

7.3. Éléments d’ordre pair

Proposition 9.
Qℓ α
Soit n = i=1 pi i la décomposition de n en produits de ℓ facteurs, avec pi ⩾ 3. La proportion d’éléments d’ordre
pair de (Z/nZ)∗ est supérieure à 1 − 21ℓ .

Démonstration. Par le théorème des restes chinois pour les éléments inversibles (théorème 6), chaque
élément x ∈ (Z/nZ)∗ est en correspondance avec un élément (x 1 , . . . , x ℓ ) où x i ∈ (Z/pαi Z)∗ . L’ordre de
x est le ppcm des ordres des x i , donc ord(x) est pair si et seulement si l’un au moins des ord(x i ) est pair.
Autrement dit ord(x) est impair si et seulement si tous les ord(x i ) sont impairs. Par la proposition 6, pour
chaque i, la proportion de x i d’ordre impair est strictement inférieure à 12 , donc la proportion de ℓ-uplets

ℓ
(x 1 , . . . , x ℓ ) dont tous les éléments sont d’ordre impair est strictement inférieure à 21 . Par complément la

ℓ
proportion d’éléments d’ordre pair dans (Z/nZ)∗ est supérieure à 1 − 21 .

7.4. Racines carrées de 1

Proposition 10.
Qℓ α
Soit n = i=1 pi i la décomposition de n en produit de ℓ facteurs, avec pi ⩾ 3. Il y a exactement 2ℓ racines
carrées de 1 modulo n.

Démonstration. Par le théorème des restes chinois pour les éléments inversibles (théorème 6), un élément
x ∈ (Z/nZ)∗ est en correspondance avec un élément (x 1 , . . . , x ℓ ) où x i ∈ (Z/pαi Z)∗ . Alors x vérifie x 2 ≡ 1
α
(mod n) si et seulement si x i2 ≡ 1 (mod pi i ), pour tout i = 1, . . . , ℓ. Par la proposition 7, il existe deux racines
carrées pour chaque i : x i = +1 ou x i = −1, ce qui donne au total 2ℓ solutions (x 1 , . . . , x ℓ ) = (±1, ±1, . . . , ±1),
donc 2ℓ racines carrées dans (Z/nZ)∗ .

8. Les hypothèses de l’algorithme de Shor

8.1. Préalable de l’algorithme de Shor

L’algorithme de Shor a pour but de factoriser un entier n. Plus précisément on souhaite trouver un facteur k
de n (autre que 1 et n). On pourra ensuite relancer l’algorithme avec nk et avec k.
Au préalable on exclut certaines situations :
• n n’est pas un entier pair. Il est très facile de tester si n est pair en vérifiant si n ≡ 0 (mod 2). Si n est
pair, alors il est divisible par 2 et c’est terminé.
• n n’est pas un nombre premier p. Il existe des tests performants pour savoir si un entier n est premier ou
pas sans calculer sa factorisation (voir le chapitre « Arithmétique »).
• n n’est pas une puissance pα d’un nombre premier. Un test simple repose sur le fait que si n = pα alors
1
α = log p (n) ⩽ log2 (n). Il suffit donc de tester si n k est un entier pour un k parmi 2, 3, . . . jusqu’à log2 (n).
COMPLÉMENTS D’ARITHMÉTIQUE 13

Dans la suite on considère donc un entier n impair, ayant au moins deux facteurs premiers distincts. On
Qℓ α
écrit sa décomposition n = i=1 pi i en produit de ℓ facteurs, avec pi ⩾ 3 premiers.

8.2. L’algorithme de Shor fonctionne au moins une fois sur deux

Hypothèse 1. L’ordre r de a modulo n est pair.
Hypothèse 2. a r/2 + 1 n’est pas divisible par n.
Théorème 7.
Qℓ α
Soit n = i=1 pi i la décomposition de n en produit de ℓ facteurs, avec pi premier et pi ⩾ 3. Alors la probabilité
1
qu’un entier a ∈ (Z/nZ)∗ vérifie l’hypothèse 1 et l’hypothèse 2 est supérieure à 1 − 2ℓ−1 .
Remarques.
• Le pire cas se produit lorsqu’il y a seulement ℓ = 2 facteurs premiers, comme dans le protocole RSA où
n = pq. Dans ce cas au moins 50% des a conviennent.
• On peut énoncer un résultat combinatoire : le nombre d’éléments a satisfaisant les hypothèses 1 et 2 est
1
supérieur à (1 − 2ℓ−1 )ϕ(n) parmi tous les ϕ(n) éléments de (Z/nZ)∗ .
• La preuve n’est pas constructive, il n’existe pas de moyen simple de calculer l’ordre de a (c’est d’ailleurs
le but de l’algorithme de Shor).

8.3. Préliminaires
On connaît déjà la proportion d’éléments a qui vérifient l’hypothèse 1. Par la proposition 9, la proportion
d’éléments d’ordre pair est supérieure à 1 − 21ℓ .
On rappelle que l’objectif de l’algorithme de Shor est de trouver la période r d’un élément a et si r est pair
d’écrire l’égalité a r ≡ 1 (mod n) sous la forme d’une factorisation :
(a r/2 − 1)(a r/2 + 1) ≡ 0 (mod n).
Cela permet de trouver un facteur de n à condition que les termes de la factorisation ci-dessus soient non
nuls.
Nous allons étudier en détails les racines carrées non-triviales de 1. Pourquoi ?
• Tout d’abord, par définition de l’ordre r, on ne peut pas avoir a r/2 ≡ 1 (mod n). Ainsi a r/2 − 1 ̸≡ 0
(mod n) et le premier terme de la factorisation est non nul.
• Supposons que l’hypothèse 2 soit vraie, c’est-à-dire a r/2 + 1 n’est pas divisible par n. Alors a r/2 + 1 ̸≡ 0
(mod n) et ainsi le second terme est non nul. Dans ce cas on a a r/2 ̸≡ −1 (mod n).
• Enfin, comme r est l’ordre de a, alors (a r/2 )2 ≡ +1 (mod n) et avec les hypothèses 1 et 2, a r/2 est une
racine carrée non-triviale de 1.

Notons R l’ensemble des racines carrées de 1 modulo n :

R = x ∈ Z/nZ | x 2 ≡ 1 (mod n) .


On rappelle que :
• Une racine carrée est nécessairement inversible (son inverse est elle-même), donc R ⊂ (Z/nZ)∗ .
• 1 et −1 sont les deux racines carrées évidentes.
• Il y a exactement 2ℓ racines carrées : Card R = 2ℓ , où ℓ est le nombre de facteurs premiers distincts de
n. Et il y a donc 2ℓ − 2 racines carrées non triviales.

8.4. Deux lemmes

Lemme 3.
Soit s ⩾ 1 et soit y ∈ (Z/nZ)∗ . L’équation x s ≡ y s (mod n), d’inconnue x, possède toujours le même nombre
de solutions quel que soit y.
COMPLÉMENTS D’ARITHMÉTIQUE 14

Démonstration. Notons S = {a1 , . . . , ad } l’ensemble des solutions de x s ≡ 1 (mod n). Alors

 ‹s
x x
x s ≡ y s (mod n) ⇐⇒ ≡ 1 (mod n) ⇐⇒ ∈ S ⇐⇒ x = ai y pour un i ∈ {1, . . . , d}.
y y
Les solutions de x s ≡ y s sont donc les d éléments {a1 y, . . . , ad y}.

Lemme 4.
S’il existe x 0 ∈ (Z/nZ)∗ tel que x 0s ≡ −1 (mod n) alors toute racine carrée z dans R peut s’écrire sous la forme
z = y s , pour un certain y ∈ (Z/nZ)∗ .
α
Démonstration. Le théorème des restes chinois fournit un isomorphisme entre (Z/nZ)∗ et (Z/p1 1 Z)∗ × · · · ×
α
(Z/pℓ ℓ Z)∗ . De plus, la proposition 10 donne la correspondance entre une racine carrée z ∈ R ⊂ (Z/nZ)∗ et
α
un élément (z1 , . . . , zℓ ) = (±1, ±1, . . . , ±1) dans le produit des (Z/pi i Z)∗ .
Le théorème des restes chinois fait correspondre x 0 à un élément (x 1 , . . . , x ℓ ) et −1 à (−1, . . . , −1). L’hypo-
α
thèse x 0s ≡ −1 (mod n) se traduit donc en x is ≡ −1 (mod pi i ).
α
Si zi = +1, alors on pose yi = +1, si zi = −1 alors on pose yi ≡ x i . Dans les deux cas on a yis ≡ zi (mod pi i )
et par isomorphisme l’élément ( y1 , . . . , yℓ ) du groupe produit correspond à y ∈ (Z/nZ)∗ tel que y s = z.

8.5. Puissance qui est une racine carrée

On ne veut pas compter les racines carrées mais le nombre d’éléments x tel que x s soit une racine carrée.
On rappelle que dans tous les cas on exclut la racine carrée 1 (qui n’a pas le bon ordre). Mais par contre
parmi les x tel que x s soit une racine carrée on veut distinguer la racine carrée −1 (qui est celle à éviter
pour avoir l’hypothèse 2).
Lemme 5.
Soit s ⩾ 1. Notons
Ss = x ∈ (Z/nZ)∗ | x s ∈ R \ {1}


et
Ss′ = x ∈ (Z/nZ)∗ | x s ∈ R \ {1, −1} .


Alors
Card Ss′ 1
⩾1− .
Card Ss 2ℓ −1

Démonstration. Dans le cas où l’équation x s ≡ −1 (mod n) n’a pas de solution, les deux ensembles Ss et Ss′
Card S ′
sont égaux, donc Card Ss = 1 et l’assertion est vraie.
s
Supposons qu’il existe x 0 tel que x 0s ≡ −1 (mod n). Soit z ∈ R, alors par le lemme 4, l’équation x s ≡ z
(mod n) est équivalente à l’équation x s ≡ y s (mod n) (pour un certain y). Par le lemme 3, cette équation
possède toujours le même nombre d de solutions (quel que soit y et donc aussi quel que soit z ∈ R). Sachant
que Card R = 2ℓ alors
Card Ss′ = d × Card(R \ {1, −1}) = d × (2ℓ − 2).
De même
Card Ss = d × Card(R \ {1}) = d × (2ℓ − 1).
Card Ss′ 2ℓ −2 1
Donc Card Ss = 2ℓ −1
=1− 2ℓ −1
.
COMPLÉMENTS D’ARITHMÉTIQUE 15

8.6. Cas favorables

Nous terminons la preuve du théorème 7.

Preuve du théorème 7. Nous avons déjà estimé dans la proposition 9, le nombre d’éléments d’ordre pair, que
l’on note P(Z/nZ)∗ :
Card P(Z/nZ)∗ 1 2ℓ − 1
⩾ 1 − = .
Card(Z/nZ)∗ 2ℓ 2ℓ
Nous allons maintenant déterminer la proportion d’éléments vérifiant l’hypothèse 2 parmi les éléments
d’ordre pair. Pour tout ordre pair r, on note s = 2r . Ainsi si un élément x est d’ordre pair r, on a (x s )2 ≡ 1
(mod n), avec x s ̸≡ 1 (mod n). Autrement dit x s ∈ R \ {1}, c’est-à-dire x ∈ Ss . Ainsi l’ensemble des éléments
ϕ(n)
d’ordre pair P(Z/nZ)∗ (c’est-à-dire satisfaisant l’hypothèse 1) est l’union des Ss (pour 1 ⩽ s ⩽ 2 ). De
plus, l’ordre étant unique, ces ensembles sont disjoints.
Notons l’ensemble des cas favorables F (Z/nZ)∗ , c’est-à-dire les éléments satisfaisant l’hypothèse 1 et
l’hypothèse 2. F (Z/nZ)∗ est simplement l’union disjointe des Ss′ .
Par le lemme 5, on a pour chaque s :
Card Ss′ 1 2ℓ − 2
⩾1− = .
Card Ss 2ℓ − 1 2ℓ − 1
Comme cette inégalité est vraie pour les ensembles indexés par s, on obtient également pour l’union :
Card F (Z/nZ)∗ 2ℓ − 2
⩾ .
Card P(Z/nZ)∗ 2ℓ − 1
Conclusion :
Card F (Z/nZ)∗ Card F (Z/nZ)∗ Card P(Z/nZ)∗ 2ℓ − 2 2ℓ − 1 2ℓ − 2 1
∗
= ∗
× ∗
⩾ ℓ
× ℓ
= ℓ
= 1 − ℓ−1 .
Card(Z/nZ) Card P(Z/nZ) Card(Z/nZ) 2 −1 2 2 2

Notes. L’explication du cas dans lequel l’ordre n’est pas une puissance de 2 est basée sur l’article Shor’s
algorithm for factoring large integers par C. Lavor, L.R.U. Manssur, R. Portugal. Il n’est pas facile de trouver
une référence exacte et complète pour le comptage des cas favorables (théorème 7). La preuve donnée ici est
reprise de « Introduction à l’informatique quantique » par Y. Leroyer et G. Sénizergues à l’Enseirb-Matmeca.