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=g₀+g₁x^q+...+g_n-1x^q(n-1). En notant ainsi la réduction modulo $f\,$ des monômes x^jq :

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

Portail des mathématiques

Ce document provient de « Algorithme de Berlekamp ».

Catégories : Corps fini | Algorithme | Calcul formel

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

Dictionnaires et Encyclopédies sur 'Academic'

Algorithme de berlekamp