Une version efficace et simple de l'algorithme de Berlekamp

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)$.