Algorithme de Berlekamp

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant l'algèbre.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

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.

[modifier] Description

L'algorithme exige de travailler sur un polynôme f(x) sans facteur carré. 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 considéré. 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 g, on en conclut qu'il divise P.

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₀+g₁x+...+g_n-1x^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ⁱ, pour i allant de 0 jusqu'à 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₁f₂, 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² tels couples, et seulement q éléments triviaux, cela montre qu'il existe des éléments non triviaux.