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

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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.

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

On pose ${\displaystyle P(X)=2^{2}Q({\dfrac {X}{2}})}$. Ainsi, ${\displaystyle P=X^{3}+X+1~mod~3}$, qui est bien unitaire. Pour se ramener à un polynôme sans facteur carré, on divise par ${\displaystyle pgcd(P,P')}$. Ici, ${\displaystyle P}$ est déjà sans facteur carré. Une fois décomposé ${\displaystyle P}$, on remonte à la décomposition de ${\displaystyle Q}$ comme suit : si ${\displaystyle P=FG}$, on a ${\displaystyle Q(X)={\dfrac {P(2X)}{2^{2}}}={\dfrac {F(2X)G(2X)}{2^{2}}}}$ , ce qui donne une factorisation de ${\displaystyle Q}$.

Pour calculer la matrice de l’application ${\displaystyle M~:~a\mapsto a^{3}-a}$, on calcule l’image des vecteurs de base de l’algèbre de Berlekamp, soit ${\displaystyle 1,X,X^{2}}$. On va donc être amené à calculer ${\displaystyle X^{3}}$ et ${\displaystyle X^{6}}$ modulo ${\displaystyle P}$. On a :

${\displaystyle X^{3}=-X-1}$

${\displaystyle X^{4}=-X^{2}-X}$

${\displaystyle X^{5}=-X^{2}+X+1}$

${\displaystyle X^{6}=X^{2}-X+1}$

La matrice de ${\displaystyle M}$ dans la base canonique est donc : ${\displaystyle \left({\begin{array}{c c c}0&-1&1\\0&1&-1\\0&0&0\\\end{array}}\right)}$

Le polynôme ${\displaystyle g=X^{2}+X}$, non constant, est dans le noyau de cette matrice.

${\displaystyle P=pgcd((X^{2}+X),P)*pgcd((X^{2}+X-1),P)*pgcd((X^{2}+X+1),P)=(X-1)(X^{2}+X-1)}$

Or cette décomposition est composée de facteurs irréductibles (on peut s’en assurer en appliquant l’algorithme à chaque facteur). Donc ${\displaystyle Q=(2X^{2}+X+1)(X+1)}$.

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 (donc aussi pour des coefficients rationnels), qui utilise aussi le lemme de Hensel et l'algorithme LLL. En effet, intuitivement, en choisissant un ${\displaystyle q}$ suffisamment grand, les opérations ne seront pas réduites modulo q ce qui permettra d'avoir la factorisation attendue. Une borne minimale pour un tel ${\displaystyle q}$ peut être obtenu grâce aux bornes de Landau-Mignotte.

• (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)
• Michel Demazure, Cours d'algèbre : primalité, divisibilité, codes [détail des éditions]
• (en) Donald Knuth, The art of computer programming/Seminumerical Algorithms, t. 2, Addison Wesley, 1981 (ISBN 0-201-03822-6), p. 421-425
• (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)

• Portail de l’algèbre
• Portail de l'informatique théorique