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 :
  • Auteur :
  • Remarque :
    122,123,141,142,148 selon moi. Un de mes développements préférés pour le fait qu'on navigue entre théorie des anneaux, théorie des corps, et algèbre linéaire.

    Questions qu'on m'a posé sur ce développement :
    - En terme de réduction, en quoi consiste l'algorithme ? (On étudie la multiplicité géométrique de la valeur propre 1 de Frob^n)
    - Appliquer l'algorithme à X^4+1 sur F_p, p premier plus grand que 3 (X^4 congrue à -1 (mod p), étudier les cas p congru à 1 mod 4, et p congru à 3 mod 4)
  • 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 299 versions au total)
L'oral à l'agrégation de mathématiques - Une sélection de développements , Isenmann, Pecatte (utilisée dans 169 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 120 versions au total)
Algèbre et calcul formel, Loïc Foissy, Alain Ninet (utilisée dans 3 versions au total)