Algorithme de Berlekamp

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.

DescriptionModifier

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é strictement inférieur à 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.


Un exempleModifier

On applique l'algorithme au polynôme  , que l'on va factoriser dans  .

Première étape : Mise sous forme unitaire sans facteur carréModifier

On pose  . Ainsi,  , qui est bien unitaire. Pour se ramener à un polynôme sans facteur carré, on divise par  . Ici,   est déjà sans facteur carré. Une fois décomposé  , on remonte à la décomposition de   comme suit : si  , on a   , ce qui donne une factorisation de  .

Deuxième étape : Calcul de la matriceModifier

Pour calculer la matrice de l’application  , on calcule l’image des vecteurs de base de l’algèbre de Berlekamp, soit  . On va donc être amené à calculer   et   modulo  . On a :

 

 

 

 

La matrice de   dans la base canonique est donc :  

Troisième étape : Calcul du noyauModifier

Le polynôme  , non constant, est dans le noyau de cette matrice.

Quatrième étape : FactorisationModifier

 

Or cette décomposition est composée de facteurs irréductibles (on peut s’en assurer en appliquant l’algorithme à chaque facteur). Donc  .

Complexité de l’algorithmeModifier

La recherche d’un facteur non constant d’un polynôme P de degré n dans   est en  .

ApplicationsModifier

Une application importante de l’algorithme de Berlekamp réside dans le calcul informatique de logarithmes discrets sur les corps finis    est un nombre premier et   un nombre entier naturel supérieur ou égal à 2. Le calcul de logarithmes discrets est une problématique importante pour la cryptographie asymétrique et les codes correcteurs. Pour un corps fini, la méthode la plus rapide est l'algorithme de calcul d'indice (en), qui inclut la factorisation des éléments du corps. Si l'on représente le corps   de manière courante - c’est-à-dire, en tant que polynômes du corps  , réduits modulo un polynôme irréductible de degré   - alors, il s’agit d’une simple factorisation polynomiale, telle qu’obtenue avec l’algorithme de Berlekamp.

D'autre part, l'algorithme de Berlekamp constitue la première étape de la factorisation de polynômes à coefficients entiers, qui utilise aussi le lemme de Hensel et l'algorithme LLL.

RéférencesModifier