s
19 708 Pages

en mathématiques l 'algorithme Berlekamp est un algorithme à la factorisation polynômes sur un champ fini conçu par Elwyn Berlekamp en 1967. L'algorithme consiste principalement à la construction d'une matrice appropriée contenant les coefficients obtenus à partir de ceux du polynôme être pris en compte et le calcul de plus grand commun diviseur polynomiale. Il était l'algorithme principal polynômes d'affacturage jusqu'à la mise en œuvre de l'algorithme de Cantor-Zassenhaus en 1981 dont il a été supplanté dans de nombreuses applications. Cependant, la méthode est encore mis en œuvre dans de nombreux systèmes d'algèbre informatique, y compris PARI / GP, en fait, est de construction simple, plusieurs étapes peuvent être parallélisé efficacement et nécessite peu d'hypothèses sur le polynôme à être prises en compte[1].

Description de l'algorithme

Étant donné un polynôme qualité à coefficients dans Galois et qu'il est dépourvu de facteurs répétés, vous recherchez un polynôme qu'il partage . puis en répétant le processus pour les facteurs ainsi obtenu, il est possible d'obtenir la factorisation en polynômes irréductibles (Ce qui est essentiellement unique, parce que chaque anneau de polynômes sur un champ fini est un anneau factoriel).

les facteurs appartiennent certainement à 'anneau quotient ; l'algorithme se concentre sur la recherche de polynômes qui répondent à la congruence

Ces polynômes forment un sous-algèbre de (Vu que espace vectoriel de taille sur ), A déclaré Berlekamp sous-algèbre. L'intérêt pour cette sous-algèbre est que tout polynôme Elle satisfait l'identité

qui est une factorisation . Cependant, nous constatons que tous les facteurs produttoria ne sont pas négligeables (par exemple éléments inversibles ou multiples de ), Mais la variation de et quelqu'un est certainement, à moins que Il n'est pas irréductible.

Pour construire est suffisante les éléments de la sous-algèbre Berlekamp pour construire une base; Ceci est possible parce que c'est le sottolagebra noyau d'une matrice à coefficients dans . Cette matrice, qui sera notée , est construit: l'élément dans '-ième rangée et -la colonne est le coefficient de la monôme qualité polynôme [2] forme , à savoir:

Ensuite, si tout polynôme Il est associé de manière bijective le vecteur ligne , il est relativement facile de prouver que le transporteur Il correspond au polynôme forme . Il en résulte qu'un polynôme appartient à la sous-algèbre Berlekamp si et seulement si est un vecteur propre de , qui satisfait le système équations inconnues (où est la matrice d'identité afin de ), Qui peut être résolu de manière efficace, par exemple en appliquant la Procédé d'élimination de Gauss, pour obtenir les polynômes recherchés.

Une fois identifié un polynôme avec la propriété demandée est suffisante pour calculer le plus grand commun diviseur entre et varier de en (Par exemple, avec le 'L'algorithme d'Euclide): Tout polynôme obtenu est un facteur , peut-être trivial.

Élimination des facteurs répétés

Pour les fonctions décrites procédure, l'hypothèse selon laquelle il est essentiel n'a pas des facteurs répétés. Toutefois, cela ne limite pas l'application de l'algorithme car il est possible d'identifier la présence de ces facteurs de manière très simple en utilisant les propriétés de dérivé formel. Les deux fait et un polynôme ses dérivés formels et calculs . Vous avez alors trois cas:

  1. si Il est une constante, puis Il est dépourvu de facteurs répétés;
  2. si , puis Il est une puissance -e, où est le caractéristique de ;
  3. si a plus grand degré de 1, alors il est un facteur de .

Factorisation des nombres entiers dans la bague

L'algorithme de Berlekamp peut également être utilisé dans la factorisation de polynômes avec des coefficients entiers. Ce problème est beaucoup plus difficile que la factorisation , Il est l'ensemble des coefficients infinis. Il est en fait même pas évident que ce problème est décidable. En fait, alors que dans on pourrait procéder à factorisation d'un polynôme de degré divisé par tous polynômes de degré inférieur ou égal à (Une technique totalement impraticable, mais correct du moins d'un point de vue théorique), en vous devez appliquer un raisonnement plus complexe que la méthode Kronecker. Cependant, vous pouvez prouver qu'il ya une première et un naturel de telle sorte que par factorisation sur les champs , , ..., , vous pouvez obtenir une factorisation aussi . Sous cette forme, la méthode est appelée algorithme Berlekamp-Zassenhaus et nécessite l'utilisation d'observations théoriques plus sophistiquées, y compris le lemme de Hensel.

notes

  1. ^ Dans l'algorithme de Cantor-Zassenhaus il est en effet nécessaire que le polynôme a donné un des facteurs de factorisation de degré égal. Toutefois, cette condition ne limite pas l'applicabilité du champ de l'algorithme, car il existe des méthodes efficaces pour la détermination d'une factorisation d'un polynôme en facteurs (pas nécessairement irréductible) qu'ils ont les propriétés requises.
  2. ^ Vous devez prêter attention au fait que les lignes et les colonnes Ils sont numérotés à , tandis que les coefficients des polynômes de à .

bibliographie

  • Elwyn Berlekamp, Affacturage Polynomials sur les corps finis, en Bell Systems Journal technique, vol. 46, 1967 pp. 1853-1859.
  • Donald Knuth, 4.6.2 factorisation des polynômes, en Les algorithmes Seminumerical, vol. 2, Reading, Addison-Wesley, 1997 ISBN 0-201-89684-2.