- 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.
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.
DémonstrationOn 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
Enfin, si tous les facteurs étaient triviaux, l'un d'eux serait, 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
.
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=g0+g1xq+...+gn-1xq(n-1). En notant ainsi la réduction modulo
des monômes xjq :
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.
DémonstrationPar 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 :
tels couples, et seulement
éléments triviaux, cela montre qu'il existe des éléments non triviaux.
Références
Michel Demazure, Cours d'algèbre. Primalité Divisibilité. Codes [détail des éditions]
Wikimedia Foundation. 2010.