Algorithme de Berlekamp - Définition

Introduction

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

L'algorithme exige de travailler sur un polynôme sans facteur carré, c'est-à-dire que les exposants des facteurs dans la décomposition en irréductibles de valent tous 1. On note son degré, et 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 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 , on peut alors former le produit , qui vaut  ; dès que le degré de est plus petit que , un des facteurs du produit est non trivial.

On remarque d'abord que les polynômes , 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 , ce qui montre que le produit divise .

Réciproquement, notons , et le produit des polynômes , pour décrivant le corps de base. Les polynômes dérivés valent tous deux  : c'est évident pour , quant à , 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 est racine commune de et de , ce qui permet de conclure que . Le polynôme divisant par définition de l'algèbre de Berlekamp, il divise , puis le produit des pgcd de et des .

Enfin, si tous les facteurs étaient triviaux, l'un d'eux serait lui-même, c'est-à-dire qu'il existerait tel que le pgcd de et serait , ce qui montrerait que le degré de serait au moins égal à .

 

On a ainsi décomposé le polynôme en produit de facteurs, dont l'un est non trivial : on a factorisé . 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 non triviaux dans l'algèbre de Berlekamp, on part du constat que la puissance -ème d'un polynôme , à coefficients dans , s'écrit g(x)^q=g₀+g₁x^q+...+g_n-1x^q(n-1). En notant ainsi la réduction modulo des monômes x^jq :

on obtient alors :

Les monômes , pour , forment une -base de l'espace vectoriel , on obtient donc par identification des coefficients, que 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 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 est irréductible.

Par contraposition, on montre que, si est un polynôme admettant une factorisation non triviale , 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 tels couples, et seulement éléments triviaux, cela montre qu'il existe des éléments non triviaux.