Travaux pratiques
5. On va maintenant introduire une variante probabiliste de l’algorithme précédent qui améliore le temps de calcul. Pour simplifier, on suppose p = 2
(l’algorithme est différent dans ce cas particulier ; voir [28]).
L’idée est la suivante : on choisit au hasard une combinaison linéaire a des éléments de la base S (les coefficients étant choisis par des tirages indépendants).
Les a mod P i sont donc des éléments aléatoirement uniformément distribués
sur F p , indépendamment pour tout i. Alors, si cette combinaison est non nulle,
soit pgcd(a, P ) est un facteur non trivial de P et l’on a gagné, soit a
p−1
2
≡ ±1
mod P i pour tout i et chaque cas se produit avec la probabilité 1/2, indépendamment pour chaque indice i (résultat classique sur les carrés dans le corps
F p , cf. TR.IX.A). Il y a beaucoup de chances pour que pgcd(a
p−1
2 − 1, P ) soit
un facteur non trivial de P : il faut et suffit pour cela qu’il existe deux indices
distincts i et j tels que a
p−1
2 − 1 ≡ 0 mod P i et a
p−1
2 − 1 ≡ 0 mod P j .
Écrire une procédure test:=proc(P,p,S,N) renvoyant, pour N tirages, la proportion q 1 de cas où pgcd(a, P ) est un facteur non trivial de P et la proportion q 2 de cas où pgcd(a
p−1
2
− 1, P ) est un facteur non trivial de P parmi les
cas où pgcd(a, P ) = 1. Tester avec P = x 4 + 1 et p = 17. Enfin, calculer
les probabilités théoriques correspondantes et comparer sur l’exemple avec les
proportions obtenues.
6. Même si la probabilité d’obtenir un facteur irréductible est élevée, il est nécessaire de vérifier qu’il en est bien ainsi : c’est là qu’intervient la procédure irreductible? de la première partie. Écrire une procédure Berlekamp2
renvoyant la factorisation obtenue par cette variante probabiliste. On modifiera Berlekamp1, les facteurs D de la liste L étant cette fois de la forme
pgcd(a, P ) = 1 ou pgcd(a
p−1
2 − 1, P ).
Remarque. Il est difficile de mettre en évidence avec Maple que la variante
probabiliste est meilleure car l’arithmétique élémentaire (pour les entiers et les
polynômes) n’est pas implémentée de façon optimale dans Maple. De plus, il
faudrait optimiser l’exponentiation.
Factorisation sur Q
On suppose P à coefficients entiers. Comme pour F p , la première étape consiste
à écrire la décomposition sans facteur carré de P , i.e. P = λh 1
1 h 2
2 . . . h s
s où λ est
le coefficient dominant de P et les h i ∈ Q[x] sont unitaires sans facteur carré et
premiers deux à deux.
255
5. On va maintenant introduire une variante probabiliste de l’algorithme précédent qui améliore le temps de calcul. Pour simplifier, on suppose p = 2
(l’algorithme est différent dans ce cas particulier ; voir [28]).
L’idée est la suivante : on choisit au hasard une combinaison linéaire a des éléments de la base S (les coefficients étant choisis par des tirages indépendants).
Les a mod P i sont donc des éléments aléatoirement uniformément distribués
sur F p , indépendamment pour tout i. Alors, si cette combinaison est non nulle,
soit pgcd(a, P ) est un facteur non trivial de P et l’on a gagné, soit a
p−1
2
≡ ±1
mod P i pour tout i et chaque cas se produit avec la probabilité 1/2, indépendamment pour chaque indice i (résultat classique sur les carrés dans le corps
F p , cf. TR.IX.A). Il y a beaucoup de chances pour que pgcd(a
p−1
2 − 1, P ) soit
un facteur non trivial de P : il faut et suffit pour cela qu’il existe deux indices
distincts i et j tels que a
p−1
2 − 1 ≡ 0 mod P i et a
p−1
2 − 1 ≡ 0 mod P j .
Écrire une procédure test:=proc(P,p,S,N) renvoyant, pour N tirages, la proportion q 1 de cas où pgcd(a, P ) est un facteur non trivial de P et la proportion q 2 de cas où pgcd(a
p−1
2
− 1, P ) est un facteur non trivial de P parmi les
cas où pgcd(a, P ) = 1. Tester avec P = x 4 + 1 et p = 17. Enfin, calculer
les probabilités théoriques correspondantes et comparer sur l’exemple avec les
proportions obtenues.
6. Même si la probabilité d’obtenir un facteur irréductible est élevée, il est nécessaire de vérifier qu’il en est bien ainsi : c’est là qu’intervient la procédure irreductible? de la première partie. Écrire une procédure Berlekamp2
renvoyant la factorisation obtenue par cette variante probabiliste. On modifiera Berlekamp1, les facteurs D de la liste L étant cette fois de la forme
pgcd(a, P ) = 1 ou pgcd(a
p−1
2 − 1, P ).
Remarque. Il est difficile de mettre en évidence avec Maple que la variante
probabiliste est meilleure car l’arithmétique élémentaire (pour les entiers et les
polynômes) n’est pas implémentée de façon optimale dans Maple. De plus, il
faudrait optimiser l’exponentiation.
Factorisation sur Q
On suppose P à coefficients entiers. Comme pour F p , la première étape consiste
à écrire la décomposition sans facteur carré de P , i.e. P = λh 1
1 h 2
2 . . . h s
s où λ est
le coefficient dominant de P et les h i ∈ Q[x] sont unitaires sans facteur carré et
premiers deux à deux.
255