7.6 Exercices
243
17. Soit E n = {1, . . . , n − 1}.
a) Soit n = 13. V´ erifier en calculant explicitement J(a, n) et a
n−1
2
(mod n) que
tout a ∈ E n satisfait ` a (7.4).
b) Soit maintenant n = 15. Combien de a ∈ E n ne satisfont pas au test ?
18. On veut utiliser l’algorithme de Shor pour trouver un diviseur de 91. Pour cela,
on choisit a = 15.
a) Calculer l’ordre de a, c’est-` a-dire le plus petit exposant entier s tel que a
s
≡
1 (mod 91). V´ erifier que s est pair.
b) Construire r ≡ a
s
2 (mod 91) et montrer que ni r − 1 ni r + 1 ne sont divisibles
par 91.
c) Suivre la d´ emarche de l’algorithme de Shor pour trouver un diviseur de 91 `
a
partir de r.
19. On veut utiliser l’algorithme de Shor pour factoriser 30. Pour cela, on choisit a au
hasard dans {1, 2, . . . , 29} et on applique la proc´ edure. Donner les a qui permettent
de trouver un diviseur propre de 30 et, dans chaque cas, d´ ecrire quelle a ´ et´ e la
m´ ethode utilis´ ee.
243
17. Soit E n = {1, . . . , n − 1}.
a) Soit n = 13. V´ erifier en calculant explicitement J(a, n) et a
n−1
2
(mod n) que
tout a ∈ E n satisfait ` a (7.4).
b) Soit maintenant n = 15. Combien de a ∈ E n ne satisfont pas au test ?
18. On veut utiliser l’algorithme de Shor pour trouver un diviseur de 91. Pour cela,
on choisit a = 15.
a) Calculer l’ordre de a, c’est-` a-dire le plus petit exposant entier s tel que a
s
≡
1 (mod 91). V´ erifier que s est pair.
b) Construire r ≡ a
s
2 (mod 91) et montrer que ni r − 1 ni r + 1 ne sont divisibles
par 91.
c) Suivre la d´ emarche de l’algorithme de Shor pour trouver un diviseur de 91 `
a
partir de r.
19. On veut utiliser l’algorithme de Shor pour factoriser 30. Pour cela, on choisit a au
hasard dans {1, 2, . . . , 29} et on applique la proc´ edure. Donner les a qui permettent
de trouver un diviseur propre de 30 et, dans chaque cas, d´ ecrire quelle a ´ et´ e la
m´ ethode utilis´ ee.