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

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

Démonstration

On remarque d'abord que les polynômes g(x) – s sont deux à deux premiers entre eux donc, en notant P(x) leur produit :

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

Or P(x) est égal à M(g(x)) avec

$M(y):=\prod _{s\in \mathbb {F} _{q}}(y-s)=y^{q}-y,$

la dernière égalité étant due au fait que ces deux polynômes sont unitaires, de degré q et nuls sur F_q.

Le polynôme P est donc égal à g^q – g. Par conséquent, pgcd(f, P) = f si et seulement si f divise g^q – g, c'est-à-dire si g est dans l'algèbre de Berlekamp.

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 :

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

on obtient alors :

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

${\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 :

$\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é

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

Un exemple

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

Première étape : Mise sous forme unitaire sans facteur carré

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

Deuxième étape : Calcul de la matrice

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

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

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

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

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

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

Troisième étape : Calcul du noyau

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

Quatrième étape : Factorisation

$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 $Q=(2X^{2}+X+1)(X+1)$.

Complexité de l’algorithme

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

Démonstration

Rappelons d’abord que pour deux polynômes P et Q, la complexité de la division euclidienne de P par Q est de l’ordre de $O(deg(q)(deg(p)-deg(q)+1))$ et celle du pgcd est en $O(deg(p)deg(q))$.

La première étape de l’algorithme est donc en $O(n^{2})$.

Ensuite, le calcul de la matrice consiste alors à faire $n$ divisions euclidiennes de polynômes, dont le degré est majoré par $nq$, par P. Cette étape est alors en $O(n(n(nq-n+1)))=O(qn^{3})$ La résolution du système de taille $n^{2}$ se fait par pivot de Gauss et a donc une complexité en $O(n^{3})$.

Enfin, il ne reste plus qu’à calculer au pire $n$ pgcd de degré au plus $n$, ce qui s’effectue en $O(n^{3})$. Finalement, on a le résultat voulu.

Applications

Une application importante de l’algorithme de Berlekamp réside dans le calcul informatique de logarithmes discrets sur les corps finis $\mathbb {F} _{p}^{n}$ où $p$ est un nombre premier et $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 $\mathbb {F} _{p}^{n}$ de manière courante - c’est-à-dire, en tant que polynômes du corps $\mathbb {F} _{p}$, réduits modulo un polynôme irréductible de degré $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.

Références

• (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 $\mathbb {Z} [X]$ », Sujet de maîtrise proposé par François Loeser,‎ 2007 (lire en ligne)