Algorithme de Berlekamp

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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

\prod_{s \in \mathbb{F}_q}{\rm pgcd}(f(x),g(x)-s)=f(x).

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 :

x^{iq}\equiv\sum_{j=0}^{n-1}\alpha_{i,j}x^j\mod\;f(x),

on obtient alors :

g(x)^q\equiv\sum_{j=0}^{n-1}(\sum_ig_i\alpha_{i,j})x^j\mod\;f(x).

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 :

\begin{pmatrix}g_0&\ldots&g_{n-1}\end{pmatrix}\begin{pmatrix}\alpha_{0,0} & \dots&\alpha_{0,n-1}\\\vdots& &\vdots\\\alpha_{n-1,0}&\dots&\alpha_{n-1,n-1}\end{pmatrix}=\begin{pmatrix}g_0&\ldots&g_{n-1}\end{pmatrix}.

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]