Algorithme de Berlekamp

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant l’algèbre
Cet article est une ébauche concernant l’algèbre.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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.

Description[modifier | modifier le code]

L'algorithme exige de travailler sur un polynôme unitaire f(x) sans facteur carré, c'est-à-dire que les exposants des facteurs dans la décomposition en irréductibles de f valent tous 1. On note n son degré et q le nombre d'éléments du corps fini Fq sur lequel on se place.

Le point central est la recherche et l'utilisation de polynômes g tels que gqg soit divisible par f. Dans l'anneau quotient Fq[x]/(f(x)), les images de ces polynômes forment une sous-Fq-algèbre, dite « algèbre de Berlekamp ». Tout élément du quotient Fq[x]/(f(x)) s'identifie à un polynôme g de degré < n et g est dans l'algèbre de Berlekamp si et seulement si

Si de plus g est non « trivial » (c'est-à-dire non constant), aucun des facteurs pgcd(f, g – s) n'est égal à f donc au moins un facteur est distinct de f et de 1. On a ainsi décomposé le polynôme f en produit de polynômes unitaires, dont l'un est distinct de f et de 1 : 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-ième d'un polynôme g(x) = g0 + g1x + … + gn–1xn–1, à coefficients dans Fq, s'écrit g(x)q = g0 + g1xq + … + gn–1xq(n–1) (cf. Endomorphisme de Frobenius). En notant ainsi la réduction modulo f des monômes xiq :

on obtient alors :

Les monômes xj, pour j = 0, … , n – 1, forment une Fq-base de l'espace vectoriel Fq[x]/(f(x)) ; 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 A des αi,j puis à tenter, par la méthode du pivot de Gauss, de trouver un vecteur ligne (g0gn–1) tel que (g0gn–1)(AIn) = 0, où In désigne la matrice identité (ou si l'on préfère : un vecteur colonne du noyau de l'application représentée par la matrice transposée, AtIn) ; si on en trouve un non trivial alors 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. Plus précisément : la dimension de cette algèbre est égale au nombre de facteurs irréductibles de f.

Références[modifier | modifier le code]