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.

Recasages pour l'année 2025 :

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 et 148.

    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 293 versions au total)
L'oral à l'agrégation de mathématiques - Une sélection de développements , Isenmann, Pecatte (utilisée dans 152 versions au total)
Cours de calcul formel. Corps finis, systèmes polynomiaux, applications , Philippe Saux Picart, Eric Rannou (utilisée dans 6 versions au total)
Cours d'algèbre , Demazure (utilisée dans 16 versions au total)
Algèbre : le grand combat: Cours et exercices, Grégory Berhuy (utilisée dans 118 versions au total)