Développement : Algorithme de Berlekamp

Détails/Enoncé :

Le but de cet algorithme est de trouver un facteur non trivial d'un polynôme $P \in \mathbb{F}_q[X]$ où $q=p^n$ est une puissance d'un nombre premier. Cet algorithme utilise l'algèbre linéaire pour trouver un polynôme $V \in \mathbb{F}_q[X]$ et $a \in \mathbb{F}_q$ tels que $\mathsf{pgcd}( P, V- a) $ soit un facteur trivial de $P$.

Ce développement se recase dans la leçon sur les anneaux principaux car on utilise la principalité de K[X] et ses propriétés arithmétiques.

Autres années :

Versions :

  • Auteur :
  • Remarque :
    D'après moi pour les leçons 122, 123, 125, 141 et 151.

    Il vaut mieux connaître la complexité approximative de l'algorithme.

    NB : tous mes développements sont généralement très détaillés car j'ai besoin de bien comprendre toutes les étapes. En l'état ils sont donc généralement trop longs pour tenir en 15 mins, et les parties "faciles" ne sont donc pas à mentionner ou juste à l'oral.
    J'écris assez mal également, toutes mes excuses.
  • Fichier :
  • Auteur :
  • Remarque :
    J'ai l'impression que dire que $P$ s'écrit comme le produit des $\mathrm{pgcd}(P,V-\alpha)$ est un peu superflu, exhiber un facteur non-trivial suffit pour enclencher la récurrence et donc ça peut vous faire gagner du temps. Sinon très bonne version dans Objectif Agrégation, comparé à la version du Demazure qui est imbitable (pour moi)
  • Référence :
  • Fichier :
  • Auteur :
  • Remarque :
    J'aime bien ce développement. Le mot "algorithme" peut faire peur mais ce n'est qu'une illusion, ce dév n'a rien d'un algorithme.

    Je le mets dans les leçons 123, 125, 141, 142 et 148. Ça fait beaucoup, à vous d'y réfléchir.

    On trouvera la preuve aux alentours de la page 244 de la référence.
  • Référence :
  • Fichier :

Références utilisées dans les versions de ce développement :

Objectif Agrégation, Beck, Malick, Peyré (utilisée dans 214 versions au total)
L'oral à l'agrégation de mathématiques - Une sélection de développements , Isenmann, Pecatte (utilisée dans 123 versions au total)