Algorithme de Berlekamp

L'algorithme exige de travailler sur un polynôme unitaire 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 tels que g^q – g soit divisible par f. Dans l'anneau quotient F_q[x]/(f(x)), les images de ces polynômes forment une sous-F_q-algèbre, dite « algèbre de Berlekamp ». Tout élément du quotient F_q[x]/(f(x)) s'identifie à un polynôme g de degré strictement inférieur à n et g est dans l'algèbre de Berlekamp si et seulement si

${\displaystyle \prod _{s\in \mathbb {F} _{q}}{\rm {pgcd}}(f(x),g(x)-s)=f(x).}$

Si de plus g est non « trivial » (c'est-à-dire non constant), aucun des facteurs pgcd(f, g – s) n'est égal à f donc au moins un facteur est distinct de f et de 1. On a ainsi décomposé le polynôme f en produit de polynômes unitaires, dont l'un est distinct de f et de 1 : 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-ième d'un polynôme g(x) = g₀ + g₁x + … + g_n–1x^n–1, à coefficients dans F_q, s'écrit g(x)^q = g₀ + g₁x^q + … + g_n–1x^q(n–1) (cf. Endomorphisme de Frobenius). En notant ainsi la réduction modulo f des monômes x^iq :

${\displaystyle x^{iq}\equiv \sum _{j=0}^{n-1}\alpha _{i,j}x^{j}\mod \;f(x),}$

on obtient alors :

${\displaystyle g(x)^{q}\equiv \sum _{j=0}^{n-1}(\sum _{i}g_{i}\alpha _{i,j})x^{j}\mod \;f(x).}$

Les monômes x^j, pour j = 0, … , 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 :

${\displaystyle {\begin{pmatrix}g_{0}&\ldots &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}&\ldots &g_{n-1}\end{pmatrix}}.}$

L'algorithme consiste donc à calculer la matrice A des α_i,j puis à tenter, par la méthode du pivot de Gauss, de trouver un vecteur ligne (g₀ … g_n–1) tel que (g₀ … g_n–1)(A – I_n) = 0, où I_n désigne la matrice identité (ou si l'on préfère : un vecteur colonne du noyau de l'application représentée par la matrice transposée, A^t – I_n) ; si on en trouve un non trivial alors 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. Plus précisément : la dimension de cette algèbre est égale au nombre de facteurs irréductibles de f.

Démonstration

Soient f₁, … , f_k les polynômes unitaires irréductibles distincts dont f est le produit. Par le théorème des restes chinois, on a un isomorphisme de F_q-algèbres :

${\displaystyle \mathbb {F} _{q}[x]/(f)\simeq \mathbb {F} _{q}[x]/(f_{1})\oplus \ldots \oplus \mathbb {F} _{q}[x]/(f_{k}).}$

Tout polynôme g ayant ses k composantes constantes dans cette décomposition est bien sûr dans l'algèbre de Berlekamp mais aussi, réciproquement, si g est dans l'algèbre, l'identité

${\displaystyle g^{q}-g=\prod _{s\in \mathbb {F} _{q}}(g-s)}$

(déjà justifiée et utilisée dans la démonstration précédente) montre que chaque f_i divise l'un des g – s. Le cardinal de cette algèbre est par conséquent q^k donc sa dimension sur F_q est k.

On applique l'algorithme au polynôme ${\displaystyle Q=2X^{3}+2X+1}$, que l'on va factoriser dans ${\displaystyle \mathbb {F} _{3}}$.

La recherche d’un facteur non constant d’un polynôme P de degré n dans ${\displaystyle \mathbb {F} _{q}}$ est en ${\displaystyle O(qn^{3})}$.

Une application importante de l’algorithme de Berlekamp réside dans le calcul informatique de logarithmes discrets sur les corps finis ${\displaystyle \mathbb {F} _{p}^{n}}$ où ${\displaystyle p}$ est un nombre premier et ${\displaystyle n}$ un nombre entier naturel supérieur ou égal à 2. Le calcul de logarithmes discrets est une problématique importante pour la cryptographie asymétrique et les codes correcteurs. Pour un corps fini, la méthode la plus rapide est l'algorithme de calcul d'indice (en), qui inclut la factorisation des éléments du corps. Si l'on représente le corps ${\displaystyle \mathbb {F} _{p}^{n}}$ de manière courante - c’est-à-dire, en tant que polynômes du corps ${\displaystyle \mathbb {F} _{p}}$, réduits modulo un polynôme irréductible de degré ${\displaystyle n}$ - alors, il s’agit d’une simple factorisation polynomiale, telle qu’obtenue avec l’algorithme de Berlekamp.

D'autre part, l'algorithme de Berlekamp constitue la première étape de la factorisation de polynômes à coefficients entiers, qui utilise aussi le lemme de Hensel et l'algorithme LLL.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Berlekamp's algorithm » (voir la liste des auteurs).
• (en) E. R. Berlekamp, « Factoring Polynomials Over Finite Fields », Bell Syst. Tech. J., vol. 46, n^o 8,‎ 1967, p. 1853-1859 (DOI 10.1002/j.1538-7305.1967.tb03174.x, lire en ligne)
• Michel Demazure, Cours d'algèbre : primalité, divisibilité, codes [détail des éditions]
• (en) Rudolf Lidl et Harald Niederreiter, Introduction to Finite Fields and Their Applications, CUP, 1994, 416 p. (ISBN 978-0-521-46094-1, présentation en ligne), p. 133-141
• Abuaf Roland et Boyer Ivan, « Factorisation dans ${\displaystyle \mathbb {Z} [X]}$ », Sujet de maîtrise proposé par François Loeser,‎ 2007 (lire en ligne)