Algorithme de Cantor-Zassenhaus
# Algorithme de Cantor-Zassenhaus

L'algorithme de Cantor-Zassenhaus est un algorithme de factorisation des polynômes à coefficients dans un corps fini. Il a été découvert par David G. Cantor (en) et Hans Julius Zassenhaus en 1981. Un autre algorithme effectuant cette opération est l'algorithme de Berlekamp, qui date de 1967.

## Préparation

L'algorithme fonctionne sur des polynômes sans facteur carré, et dont tous les facteurs irréductibles ont même degré. La première condition est habituelle, et l'on s'y ramène en considérant le pgcd du polynôme et de son polynôme dérivé. Quant à la deuxième condition, elle est traitée grâce au fait que tous les polynômes irréductibles de degré divisant n, à coefficients dans un corps fini de cardinal q, sont des diviseurs du polynôme $X^{qn}$ – X.

Soit f un polynôme sans facteur carré à factoriser. L'algorithme de Cantor-Zassenhaus implique donc de calculer d'abord le pgcd de f et $X^q$ – X c'est un produit de polynômes de degré 1, auxquels on applique le pas général de l'algorithme ; on divise ensuite f par tous ses facteurs de degré 1, et on recommence en calculant le pgcd du quotient avec $X^{q2}$ – X, en divisant par les facteurs trouvés, et en continuant jusqu'à épuisement des facteurs irréductibles de f.

## Pas général de l'algorithme

On suppose ici que f est un polynôme à coefficients dans le corps fini $F_q$ à q éléments, sans facteur carré et dont tous les facteurs irréductibles sont de même degré d, fixé à l'avance. Notons $f_1,$ jusqu'à $f_r$ ces facteurs irréductibles. Alors, par le théorème des restes chinois, il existe un isomorphisme :

    $\mathbb {F} _{q}[x]/(f)\simeq \mathbb {F} _{q}[x]/(f_{1})\oplus \dots \oplus \mathbb {F} _{q}[x]/(f_{r})$

On cherche alors un polynôme a(x), dont la réduction modulo $f_i$ sera notée $a_i$ pour chaque i, tel que tous les $a_i$ valent 0, 1 ou –1, et tel que deux au moins des ensembles suivants sont non vides :

    $A=\{i\mid a_{i}(x)=0\},$
    $B=\{i\mid a_{i}(x)=-1\},$
    $C=\{i\mid a_{i}(x)=1\}.$

Alors, les polynômes suivant fournissent une factorisation non triviale de f :

    ${\rm {pgcd}}(f(x),a(x))=\prod _{i\in A}p_{i}(x),$
    ${\rm {pgcd}}(f(x),a(x)-1)=\prod _{i\in B}p_{i}(x),$
    ${\rm {pgcd}}(f(x),a(x)+1)=\prod _{i\in C}p_{i}(x).$

Il faudra alors appliquer ce pas général récursivement aux facteurs trouvés jusqu'à obtenir des facteurs de degré d. En caractéristique différente de 2, un polynôme a(x) est trouvé en constatant que chaque $F_q[x]/(f_i)$ est un corps fini de cardinal $q^d,$ et que donc, en choisissant b(x) de degré plus petit que d, et différent des polynômes constants 0, 1 et –1, les réductions $a_i$ du polynôme $a=b^{\frac {q^{d}-1}{2}}$ sont bien toutes 0, 1 ou –1. Il peut cependant advenir que pour le polynôme a ainsi construit, deux des trois ensembles A, B et C soient vides, mais la probabilité peut être contrôlée. L'algorithme consiste donc à tester des polynômes b choisis au hasard jusqu'à trouver un polynôme a tel que souhaité.

