Algorithme de Berlekamp

Restez toujours informé : suivez-nous sur Google (☆)

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 $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 $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 $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 F_{q}} p g c d (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.

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 $F_{q}$ , s'écrit g(x)=g₀+g₁x+...+g_n-1x. En notant ainsi la réduction modulo $f$ des monômes x :

x^{j q} = i = 0 \sum n - 1 α_{ij} x^{i} mod f (x),

on obtient alors :

g (x)^{q} = i = 0 \sum n - 1 (j \sum α_{j i} g_{j}) x^{i} .

Les monômes $x^{i}$ , pour $i = 0, \dots, n - 1$ , forment une $F_{q}$ -base de l'espace vectoriel $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.