Algorithme De Berlekamp

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 $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 $\mathbb{F}_q$ sur lequel on se place. Le point central est la recherche et l'utilisation de polynômes $g(x)\,$ tels que :

$g(x)^q-g(x)\equiv 0 \mod\;f(x)$

Ces polynômes forment une sous-algèbre, dite algèbre de Berlekamp de l'espace quotient $\mathbb{F}_q[x]/(f(x))$. 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 $g\,$, on peut alors former le produit $\prod_{s \in \mathbb{F}_q} pgcd(f(x),g(x)-s)\,$, qui vaut $f(x)\,$ ; dès que le degré de $g\,$ est plus petit que $n\,$, un des facteurs du produit est non trivial.

Démonstration

On remarque d'abord que les polynômes $g(x)-s\,$, 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 $f(x)\,$, ce qui montre que le produit divise $f(x)\,$.

Réciproquement, notons $G(x)=g(x)^q-g(x)\,$, et $P(x)\,$ le produit des polynômes $g(x)-s\,$, pour $s\,$ décrivant le corps de base. Les polynômes dérivés valent tous deux $-g'(x)\,$ : c'est évident pour $G\,$, quant à $P\,$, on vérifie :

$P'(x)=g'(x)\sum_{s\in\mathbb{F}_q}\prod_{s\neq t\in\mathbb{F}_q}(g(x)-t)=g'(x)M(x)$

et le polynôme M(x) est constamment égal à -1, car, pour α un élément du corps fini :

$M(\alpha)=\sum_{s\in\mathbb{F}_q}\prod_{s\neq t\in\mathbb{F}_q}(g(\alpha)-t)=\prod_{g(\alpha)\neq t\in\mathbb{F}_q}(g(\alpha)-t)=\prod_{0\neq t\in\mathbb{F}_q}t=-1$

en utilisant le théorème de Wilson. Sur la clôture algébrique de $\mathbb{F}_q$, on vérifie ensuite que toute racine de $g\,$ est racine commune de $G\,$ et de $P\,$, ce qui permet de conclure que $G=P\,$. Le polynôme $f\,$ divisant $G\,$ par définition de l'algèbre de Berlekamp, il divise $P\,$, puis le produit des pgcd de $f\,$ et des $g(x)-s\,$.

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

On a ainsi décomposé le polynôme $f\,$ en produit de facteurs, dont l'un est non trivial : 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\,$-ème d'un polynôme $g(x)=g_0+g_1 x+...+g_{n-1}x^{n-1}\,$, à coefficients dans $\mathbb{F}_q$, s'écrit g(x)^q=g₀+g₁x^q+...+g_n-1x^q(n-1). En notant ainsi la réduction modulo $f\,$ des monômes x^jq :

$x^{jq}=\sum_{i=0}^{n-1}\alpha_{ij}x^i\mod\;f(x),$

on obtient alors :

$g(x)^q=\sum_{i=0}^{n-1}(\sum_j\alpha_{ji}g_j)x^i.$

Les monômes $x^i\,$, pour $i =0,\ldots,n-1 \,$, forment une $\mathbb{F}_q$-base de l'espace vectoriel $\mathbb{F}_q[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\\\vdots\\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\\\vdots\\g_{n-1}\end{pmatrix}.$

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 $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.

Démonstration

Par contraposition, on montre que, si $f\,$ est un polynôme admettant une factorisation non triviale $f=f_1 f_2\,$, 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 $\mathbb{F}_q$-algèbres :

$\mathbb{F}_q[x]/(f)\simeq\mathbb{F}[x]/(f_1)\oplus\mathbb{F}[x]/(f_2),$

et tout polynôme ayant deux composantes constantes dans cette décomposition est dans l'algèbre de Berlekamp ; comme il existe $q^2\,$ tels couples, et seulement $q\,$ é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]

Ce document provient de « Algorithme de Berlekamp ».