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