Algorithme de Berlekamp

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 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 \mathbb{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 \mathbb{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 \mathbb{F}_q} pgcd(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.

Démonstration

On remarque d'abord que les polynômes g(x)-s\,, non constants, sont deux à deux premiers entre eux, ce qui montre que les facteurs du produit sont des polynômes deux à deux premiers entre eux, chacun divisant f(x)\,, ce qui montre que le produit divise f(x)\,.

Réciproquement, notons G(x)=g(x)^q-g(x)\,, et P(x)\, le produit des polynômes g(x)-s\,, pour s\, décrivant le corps de base. Les polynômes dérivés valent tous deux -g'(x)\, : c'est évident pour G\,, quant à P\,, on vérifie :

P'(x)=g'(x)\sum_{s\in\mathbb{F}_q}\prod_{s\neq t\in\mathbb{F}_q}(g(x)-t)=g'(x)M(x)

et le polynôme M(x) est constamment égal à -1, car, pour α un élément du corps fini :

M(\alpha)=\sum_{s\in\mathbb{F}_q}\prod_{s\neq t\in\mathbb{F}_q}(g(\alpha)-t)=\prod_{g(\alpha)\neq t\in\mathbb{F}_q}(g(\alpha)-t)=\prod_{0\neq t\in\mathbb{F}_q}t=-1

en utilisant le théorème de Wilson. Sur la clôture algébrique de \mathbb{F}_q, on vérifie ensuite que toute racine de g\, est racine commune de G\, et de P\,, ce qui permet de conclure que G=P\,. Le polynôme f\, divisant G\, par définition de l'algèbre de Berlekamp, il divise P\,, puis le produit des pgcd de f\, et des g(x)-s\,.

Enfin, si tous les facteurs étaient triviaux, l'un d'eux serait f\, lui-même, c'est-à-dire qu'il existerait t\, tel que le pgcd de f\, et g(x)-t\, serait f\,, ce qui montrerait que le degré de g\, serait au moins égal à n\,.
 

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 \mathbb{F}_q, s'écrit g(x)q=g0+g1xq+...+gn-1xq(n-1). En notant ainsi la réduction modulo f\, des monômes xjq :

x^{jq}=\sum_{i=0}^{n-1}\alpha_{ij}x^i\mod\;f(x),

on obtient alors :

g(x)^q=\sum_{i=0}^{n-1}(\sum_j\alpha_{ji}g_j)x^i.

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

Démonstration

Par contraposition, on montre que, si f\, est un polynôme admettant une factorisation non triviale f=f_1 f_2\,, alors l'algèbre de Berlekamp admet des éléments non triviaux. En supposant que les deux facteurs ci-dessus sont premiers entre eux, on trouve, par le théorème des restes chinois, l'isomorphisme de \mathbb{F}_q-algèbres :

\mathbb{F}_q[x]/(f)\simeq\mathbb{F}[x]/(f_1)\oplus\mathbb{F}[x]/(f_2),
et tout polynôme ayant deux composantes constantes dans cette décomposition est dans l'algèbre de Berlekamp ; comme il existe q^2\, tels couples, et seulement q\, éléments triviaux, cela montre qu'il existe des éléments non triviaux.
 

Références

Michel Demazure, Cours d'algèbre. Primalité Divisibilité. Codes  [détail des éditions]


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Berlekamp de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • Algorithme De Cantor-Zassenhaus — L algorithme de Cantor Zassenhaus est un algorithme de factorisation des polynômes à coefficients dans un corps fini Il a été découvert par D. Cantor et Hans Zassenhaus en 1981. Un autre algorithme effectuant cette opération est l algorithme de… …   Wikipédia en Français

  • Algorithme de cantor-zassenhaus — L algorithme de Cantor Zassenhaus est un algorithme de factorisation des polynômes à coefficients dans un corps fini Il a été découvert par D. Cantor et Hans Zassenhaus en 1981. Un autre algorithme effectuant cette opération est l algorithme de… …   Wikipédia en Français

  • Algorithme de Cantor-Zassenhaus — L algorithme de Cantor Zassenhaus est un algorithme de factorisation des polynômes à coefficients dans un corps fini Il a été découvert par David Cantor et Hans Julius Zassenhaus en 1981. Un autre algorithme effectuant cette opération est l… …   Wikipédia en Français

  • Algorithme de van Hoeij — En mathématiques et en algorithmique, les algorithmes de van Hoeij sont des algorithmes efficaces de factorisation des polynômes à coefficients rationnels, ou plus généralement à coefficients dans un corps de nombres ou de fonctions. Ils datent… …   Wikipédia en Français

  • Elwyn Berlekamp — Elwyn Ralph Berlekamp Naissance 6 septembre 1940 Dover (Ohio) (en …   Wikipédia en Français

  • Registre a decalage — Registre à décalage En électronique et en informatique, un registre à décalage est un registre de taille fixe dans lequel les bits sont décalés à chaque coup d horloge (dans le cas d un système synchrone sur l horloge). Un registre à décalage est …   Wikipédia en Français

  • Registre à décalage à rétroaction linéaire — Un registre à décalage à rétroaction linéaire, ou LFSR (acronyme de l anglais linear feedback shift register), est un dispositif électronique ou logiciel qui produit une suite récurrente linéaire, initialement sur le corps fini à 2 élements (0 et …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”