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 FModèle:Ind sur lequel on se place.

Le point central est la recherche et l'utilisation de polynômes g tels que gModèle:Exp – g soit divisible par f. Dans l'anneau quotient FModèle:Ind[x]/(f(x)), les images de ces polynômes forment une sous-[[Algèbre associative sur un corps|FModèle:Ind-algèbre]], dite « algèbre de Berlekamp ». Tout élément du quotient FModèle:Ind[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 {𝔽}_q}\mathrm{p}\mathrm{g}\mathrm{c}\mathrm{d}(f(x),g(x)-s)=f(x).$

Modèle:Démonstration/début On remarque d'abord que les polynômes g(x) – s sont deux à deux premiers entre eux donc, en notant P(x) leur produit :

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

la dernière égalité étant due au fait que ces deux polynômes sont unitaires, de degré q et [[Corps fini#Polynômes primitifs et polynômes cyclotomiques|nuls sur FModèle:Ind]].

Le polynôme P est donc égal à gModèle:Exp – g. Par conséquent, pgcd(f, P) = f si et seulement si f divise gModèle:Exp – g, c'est-à-dire si g est dans l'algèbre de Berlekamp. Modèle:Démonstration/fin

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 FModèle:Ind, s'écrit Modèle:Nobr (Modèle: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}modf(x),$

on obtient alors :

$g(x{)}^q\equiv \sum _{j=0}^{n-1}(\sum _i{g}_i{\alpha }_{i,j})x^{j}modf(x).$

Les monômes xModèle:Exp, pour j = 0, … , n – 1, forment une FModèle:Ind-base de l'espace vectoriel FModèle:Ind[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 :

$\left(\begin{array}{ccc}{g}_0& \dots & g_{n-1}\end{array}\right)\left(\begin{array}{ccc}{\alpha }_{0,0}& \dots & {\alpha }_{0,n-1}\\ ⋮& & ⋮\\ {\alpha }_{n-1,0}& \dots & {\alpha }_{n-1,n-1}\end{array}\right)=\left(\begin{array}{ccc}{g}_0& \dots & g_{n-1}\end{array}\right).$

L'algorithme consiste donc à calculer la matrice A des Modèle:Math 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 – IModèle:Ind) = 0, où IModèle:Ind 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, AModèle:Exp – IModèle:Ind) ; 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.

Un exemple

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

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

On pose $P(X)=2^{2}Q(\frac{X}{2})$. Ainsi, $P=X^3+X+1mod3$, qui est bien unitaire. Pour se ramener à un polynôme sans facteur carré, on divise par $pgcd(P,P^{\prime })$. 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)=\frac{P(2X)}{2^2}=\frac{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}{ccc}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 ${𝔽}_q$ est en $O(q{n}^3)$.

Applications

Une application importante de l’algorithme de Berlekamp réside dans le calcul informatique de logarithmes discrets sur les corps finis ${𝔽}_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'Modèle:Lien, qui inclut la factorisation des éléments du corps. Si l'on représente le corps ${𝔽}_p^n$ de manière courante - c’est-à-dire, en tant que polynômes du corps ${𝔽}_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

• Modèle:Article
• Modèle:Demazure1
• Modèle:Ouvrage
• Modèle:Ouvrage
• Modèle:Article

Modèle:Portail