Livre_silo 30 août 2013 16:32 Page 356
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
356
Informatique pour tous
Complexité
Déterminer la complexité de cet algorithme est un problème très difficile, mais en pratique
l’algorithme n’ est plus guère utilisable au-delà de 10
6 .
Méthode de Fermat
On se propose ici de réaliser un autre algorithme de décomposition en facteurs premiers,
dû à Pierre de Fermat (1643), plus adapté à la recherche de grands facteurs premiers.
Soit N impair s’écrivant sous la forme uv, avec u ⩽ v. On définit alors :
x = (u + v)/2,
y = (v − u)/2
et on a :
N = x
2
− y
2 ,
0 ⩽ y < x ⩽ N
La méthode de Fermat consiste à rechercher des valeurs de x et y satisfaisant les conditions
ci-dessus. Étant donné N impair, l’algorithme suivant détermine le plus grand facteur
de N inférieur ou égal à
√
N :
A1 Initialiser : x
′
← 2⌊
√
N ⌋ + 1, y
′
← 1 et r ← ⌊
√
N ⌋
2
− N
(dans la suite, x
′ correspond à 2x + 1, y
′ à 2y + 1 et r à x
2 + y
2
− N ).
A2 Si r > 0 alors faire r ← r − y
′ , y
′
← y
′ + 2. Aller en A2.
A3 Si r < 0 alors faire r ← r + x
′ , x
′
← x
′ + 2. Aller en A2.
A4 Si r = 0 alors c’est terminé : on a
N = ((x
′
− y
′ )/2)((x
′ + y
′
− 2)/2)
et (x
′
− y
′ )/2 est le plus grand facteur de N inférieur ou égal à
√
N .
Écrire une fonction fermat réalisant l’algorithme ci-dessus et renvoyant la décomposition
en deux facteurs obtenue. En déduire une nouvelle fonction decomp2 de décomposition en
facteurs premiers.
A.6.3 Recherche de grands nombres premiers
Pour déterminer si un nombre est premier, on peut évidemment utiliser les fonctions decomp
ou fermat définies précédemment. Donner une estimation (grossière) de l’entier maximum
dont on peut vérifier qu’il est premier avec ces méthodes en un temps de moins de dix
secondes. Pour vérifier que cette estimation est correcte, on pourra essayer les fonctions
decomp et fermat sur les nombres 2
p
− 1, en prenant pour p les valeurs successives 17, 19,
31, 61, 107, 127.
On s’attache maintenant à trouver une méthode plus efficace pour tester la primalité d’un
entier. On s’intéressera ici au test de Fermat.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
356
Informatique pour tous
Complexité
Déterminer la complexité de cet algorithme est un problème très difficile, mais en pratique
l’algorithme n’ est plus guère utilisable au-delà de 10
6 .
Méthode de Fermat
On se propose ici de réaliser un autre algorithme de décomposition en facteurs premiers,
dû à Pierre de Fermat (1643), plus adapté à la recherche de grands facteurs premiers.
Soit N impair s’écrivant sous la forme uv, avec u ⩽ v. On définit alors :
x = (u + v)/2,
y = (v − u)/2
et on a :
N = x
2
− y
2 ,
0 ⩽ y < x ⩽ N
La méthode de Fermat consiste à rechercher des valeurs de x et y satisfaisant les conditions
ci-dessus. Étant donné N impair, l’algorithme suivant détermine le plus grand facteur
de N inférieur ou égal à
√
N :
A1 Initialiser : x
′
← 2⌊
√
N ⌋ + 1, y
′
← 1 et r ← ⌊
√
N ⌋
2
− N
(dans la suite, x
′ correspond à 2x + 1, y
′ à 2y + 1 et r à x
2 + y
2
− N ).
A2 Si r > 0 alors faire r ← r − y
′ , y
′
← y
′ + 2. Aller en A2.
A3 Si r < 0 alors faire r ← r + x
′ , x
′
← x
′ + 2. Aller en A2.
A4 Si r = 0 alors c’est terminé : on a
N = ((x
′
− y
′ )/2)((x
′ + y
′
− 2)/2)
et (x
′
− y
′ )/2 est le plus grand facteur de N inférieur ou égal à
√
N .
Écrire une fonction fermat réalisant l’algorithme ci-dessus et renvoyant la décomposition
en deux facteurs obtenue. En déduire une nouvelle fonction decomp2 de décomposition en
facteurs premiers.
A.6.3 Recherche de grands nombres premiers
Pour déterminer si un nombre est premier, on peut évidemment utiliser les fonctions decomp
ou fermat définies précédemment. Donner une estimation (grossière) de l’entier maximum
dont on peut vérifier qu’il est premier avec ces méthodes en un temps de moins de dix
secondes. Pour vérifier que cette estimation est correcte, on pourra essayer les fonctions
decomp et fermat sur les nombres 2
p
− 1, en prenant pour p les valeurs successives 17, 19,
31, 61, 107, 127.
On s’attache maintenant à trouver une méthode plus efficace pour tester la primalité d’un
entier. On s’intéressera ici au test de Fermat.