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₁, jusqu'à f_r ces facteurs irréductibles. Alors, par le théorème des restes chinois, il existe un isomorphisme :

${\displaystyle \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 :

${\displaystyle A=\{i\mid a_{i}(x)=0\},}$

${\displaystyle B=\{i\mid a_{i}(x)=-1\},}$

${\displaystyle C=\{i\mid a_{i}(x)=1\}.}$

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

${\displaystyle {\rm {pgcd}}(f(x),a(x))=\prod _{i\in A}p_{i}(x),}$

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

${\displaystyle {\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 ${\displaystyle 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é.

Références

• (en) David G. Cantor et Hans Zassenhaus, « A New Algorithm for Factoring Polynomials Over Finite Fields », Math. Comp., vol. 36, n^o 154,‎ 1981, p. 587-592 (DOI 10.1090/S0025-5718-1981-0606517-5)
• Michel Demazure, Cours d'algèbre : primalité, divisibilité, codes [détail des éditions]