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 :