Livre_silo 30 août 2013 16:32 Page 357
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
357
A – Travaux pratiques
Test de Fermat
Soit n un entier. On dit que n passe le test de Fermat de base a si a
n−1
≡ 1[n]. On sait que
si n est premier, alors pour tout entier a ∈]0, n[, n passe le test de Fermat de base a. Donc,
par contraposée, si n ne passe pas le test de Fermat de base a, alors n n’est pas premier.
On dit dans ce cas que a est un témoin de non-primalité de n pour le test de Fermat. Si
n passe le test de Fermat de base a mais n’est pas un nombre premier, on dit que n est un
pseudo-premier de Fermat de base a.
Écrire une fonction passe_fermat(a,n) à valeur booléenne indiquant si n passe le test de
Fermat de base a.
Y a-t-il des entiers compris entre 1 et 1 000 qui soient des pseudo-premiers de Fermat de
base 2 (on les appelle aussi nombres de Poulet) ? Lesquels ?
Y a-t-il des entiers n compris entre 1 et 1 000 qui soient des pseudo-premiers de Fermat
de base a pour tout a ? Pour tout a appartenant à ]0, n[ ?
Pour tester si a
n−1 est congru à 1 modulo n, on peut calculer a**(n-1) % n. Combien de
temps ce calcul prend-il pour n = 100 000 000 et a = 2 ? Python propose une fonction
spécialisée pour effectuer ce calcul : pow. On peut calculer pow(a, n-1, n). Comparer avec le
temps d’exécution précédent.
Les nombres premiers sont très utiles en cryptographie. Le logiciel de chiffrement PGP
utilise ainsi les tests de Fermat de bases 2, 3, 5 et 7 pour décider si un nombre est premier ⁶.
Écrire une fonction premier_PGP(n) « testant » si un nombre est premier avec la méthode
utilisée par PGP.
En considérant que ce test est parfait, écrire une fonction premier_suivant(n) rendant le plus
petit nombre premier strictement supérieur à n.
Chercher expérimentalement jusqu’à quelle valeur de n on obtient une réponse en moins
de dix secondes.
Test de Miller-Rabin
On propose maintenant un autre test, appelé test de Miller-Rabin. Il fonctionne de la
façon suivante. Pour tester si un entier n est premier, on commence par écrire n − 1 sous
la forme 2
s
× m, où m est impair. Soit a ∈ 1, n − 1. Le test repose sur le résultat
suivant : si n est premier, alors ou bien a
m
≡ 1[n], ou bien il existe d ∈ 0, s − 1 vérifiant
a
2
d .m
≡ −1[n]. On peut démontrer ce résultat en utilisant le petit théorème de Fermat,
le fait que si n est premier Z/nZ est un corps et le fait que dans tout anneau intègre,
l’équation x
2 = 1 a au plus deux solutions ⁷ (1 et −1).
6. Le risque de choisir accidentellement un nombre non premier est apparemment très faible pour les plages
de nombres testées par PGP.
7. Dans certains anneaux intègres, il n’y en a qu’une, par exemple dans Z/2Z, où −1 = 1.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
357
A – Travaux pratiques
Test de Fermat
Soit n un entier. On dit que n passe le test de Fermat de base a si a
n−1
≡ 1[n]. On sait que
si n est premier, alors pour tout entier a ∈]0, n[, n passe le test de Fermat de base a. Donc,
par contraposée, si n ne passe pas le test de Fermat de base a, alors n n’est pas premier.
On dit dans ce cas que a est un témoin de non-primalité de n pour le test de Fermat. Si
n passe le test de Fermat de base a mais n’est pas un nombre premier, on dit que n est un
pseudo-premier de Fermat de base a.
Écrire une fonction passe_fermat(a,n) à valeur booléenne indiquant si n passe le test de
Fermat de base a.
Y a-t-il des entiers compris entre 1 et 1 000 qui soient des pseudo-premiers de Fermat de
base 2 (on les appelle aussi nombres de Poulet) ? Lesquels ?
Y a-t-il des entiers n compris entre 1 et 1 000 qui soient des pseudo-premiers de Fermat
de base a pour tout a ? Pour tout a appartenant à ]0, n[ ?
Pour tester si a
n−1 est congru à 1 modulo n, on peut calculer a**(n-1) % n. Combien de
temps ce calcul prend-il pour n = 100 000 000 et a = 2 ? Python propose une fonction
spécialisée pour effectuer ce calcul : pow. On peut calculer pow(a, n-1, n). Comparer avec le
temps d’exécution précédent.
Les nombres premiers sont très utiles en cryptographie. Le logiciel de chiffrement PGP
utilise ainsi les tests de Fermat de bases 2, 3, 5 et 7 pour décider si un nombre est premier ⁶.
Écrire une fonction premier_PGP(n) « testant » si un nombre est premier avec la méthode
utilisée par PGP.
En considérant que ce test est parfait, écrire une fonction premier_suivant(n) rendant le plus
petit nombre premier strictement supérieur à n.
Chercher expérimentalement jusqu’à quelle valeur de n on obtient une réponse en moins
de dix secondes.
Test de Miller-Rabin
On propose maintenant un autre test, appelé test de Miller-Rabin. Il fonctionne de la
façon suivante. Pour tester si un entier n est premier, on commence par écrire n − 1 sous
la forme 2
s
× m, où m est impair. Soit a ∈ 1, n − 1. Le test repose sur le résultat
suivant : si n est premier, alors ou bien a
m
≡ 1[n], ou bien il existe d ∈ 0, s − 1 vérifiant
a
2
d .m
≡ −1[n]. On peut démontrer ce résultat en utilisant le petit théorème de Fermat,
le fait que si n est premier Z/nZ est un corps et le fait que dans tout anneau intègre,
l’équation x
2 = 1 a au plus deux solutions ⁷ (1 et −1).
6. Le risque de choisir accidentellement un nombre non premier est apparemment très faible pour les plages
de nombres testées par PGP.
7. Dans certains anneaux intègres, il n’y en a qu’une, par exemple dans Z/2Z, où −1 = 1.