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.


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.


Références

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

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Algorithme de Berlekamp ».

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

  • 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

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Generateur de nombres pseudo-aleatoires — Générateur de nombres pseudo aléatoires Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les… …   Wikipédia en Français

Share the article and excerpts

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