Développement : Une version efficace et simple de l'algorithme de Berlekamp

Détails/Enoncé :

Prenez un polynômes $P$ à coefficients dans un corps fini de cardinal $q$. Notre but sera de le décomposer en irréductibles.

L'algorithme de Berlekamp est souvent présenté comme une sorte de théorème qui permet d'exprimer $P$ comme un produit non trivial, et on nous dit d'itérer récursivement l'algorithme afin de scinder en irréductibles chaque facteur.

Mais c'est idiot : cela demanderait beaucoup de pivots de Gauss, et dans le pire des cas, on aurait une complexité en $O(q\deg(P)^4)$ (chaque pivot a, en effet, un coût cubique).

Cette version ne fait qu'un seul pivot de Gauss. L'algorithme obtenu est très simple à écrire et entièrement suffisant pour scinder un polynôme. Il n'est pas foncièrement différent de ce qui est fait classiquement. Sa complexité est de $O(q\deg(P)^3)$.

Recasages pour l'année 2024 :

Autres années :

Versions :

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