Algorithme de Berlekamp
Un article de Wikipédia, l'encyclopédie libre.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
L'algorithme de Berlekamp est une méthode de factorisation des polynômes à coefficients dans un corps fini, qui repose sur des calculs de PGCD de polynômes et des opérations matricielles. Il a été découvert par Elwyn Berlekamp en 1967, et est resté l'algorithme le plus performant concernant ce problème jusqu'en 1981, et la découverte de l'algorithme de Cantor-Zassenhaus.
[modifier] Description
L'algorithme exige de travailler sur un polynôme f(x) sans facteur carré. On note n son degré, et q le nombre d'éléments du corps fini sur lequel on se place. Le point central est la recherche et l'utilisation de polynômes g(x) tels que :
Ces polynômes forment une sous-algèbre, dite algèbre de Berlekamp de l'espace quotient . En particulier, les images des polynômes constants seront des éléments de l'algèbre de Berlekamp ; on parlera d'élément trivial. Si un élément non trivial de l'algèbre de Berlekamp a été déterminé, provenant d'un polynôme g, on peut alors former le produit , qui vaut f(x) ; dès que le degré de g est plus petit que n, un des facteurs du produit est non trivial.
On remarque d'abord que les polynômes g(x)-s, non constants, sont deux à deux premiers entre eux, ce qui montre que les facteurs du produit sont des polynômes deux à deux premiers entre eux, chacun divisant f(x), ce qui montre que le produit divise f(x).
Réciproquement, notons G(x)=g(x)q-g(x), et P(x) le produit considéré. Les polynômes dérivés valent tous deux -g'(x) : c'est évident pour G, quant à P, on vérifie :
et le polynôme M(x) est constamment égal à -1, car, pour α un élément du corps fini :
en utilisant le théorème de Wilson. Sur la clôture algébrique de , on vérifie ensuite que toute racine de g est racine commune de G et de P, ce qui permet de conclure que G=P. Le polynôme f divisant G par définition de g, on en conclut qu'il divise P.
Enfin, si tous les facteurs étaient triviaux, l'un d'eux serait f lui-même, c'est-à-dire qu'il existerait t tel que le pgcd de f et g(x)-t serait f, ce qui montrerait que le degré de g serait au moins égal à n.
On a ainsi décomposé le polynôme f en produit de facteurs, dont l'un est non trivial : on a factorisé f. Pour obtenir une factorisation en produit de polynômes irréductibles, il suffit d'appliquer cette méthode récursivement.
Pour trouver des polynômes g non triviaux dans l'algèbre de Berlekamp, on part du constat que la puissance q-ème d'un polynôme g(x)=g0+g1x+...+gn-1xn-1, à coefficients dans , s'écrit g(x)q=g0+g1xq+...+gn-1xq(n-1). En notant ainsi la réduction modulo f des monômes xjq :
on obtient alors :
Les monômes xi, pour i allant de 0 jusqu'à n-1, forment une -base de l'espace vectoriel , on obtient donc par identification des coefficients, que g est un élément de l'algèbre de Berlekamp si et seulement si l'identité matricielle suivante est vérifiée :
L'algorithme consiste donc à calculer la matrice des αi,j, à tenter, par la méthode du pivot de Gauss, de trouver un vecteur dans le noyau de cette matrice à laquelle a été soustraite la matrice identité ; si on en trouve un, on peut factoriser f par des calculs de pgcd, via l'algorithme d'Euclide. Enfin, on montre que s'il n'existe pas d'élément non trivial dans l'algèbre de Berlekamp, alors le polynôme f est irréductible.
Par contraposition, on montre que, si f est un polynôme admettant une factorisation non triviale f=f1f2, alors l'algèbre de Berlekamp admet des éléments non triviaux. En supposant que les deux facteurs ci-dessus sont premiers entre eux, on trouve, par le théorème des restes chinois, l'isomorphisme de -algèbres :
et tout polynôme ayant deux composantes constantes dans cette décomposition est dans l'algèbre de Berlekamp ; comme il existe q2 tels couples, et seulement q éléments triviaux, cela montre qu'il existe des éléments non triviaux.
[modifier] Références
Michel Demazure, Cours d'algèbre. Primalité Divisibilité. Codes [détail des éditions]