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 D. Cantor et Hans 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 premiers ont même degré. La première condition est habituelle, et 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 premiers de f.

Pas général de l'algorithme

On suppose ici que f est un polynôme à coefficients dans le corps fini $\mathbb{F}_q$ à q éléments, sans facteur carré et dont tous les facteurs premiers sont de même degré d, fixé à l'avance. Notons f₁, jusqu'à f_r ces facteurs premiers. 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 | a_i(x) = 0},

B = {i | a_i(x) = − 1},

C = {i | a_i(x) = 1},

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

$pgcd(f(x),a(x)) = \prod_{i \in A} p_i(x)$,

$pgcd(f(x),a(x)-1) = \prod_{i \in B} p_i(x)$,

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

Référence

Michel Demazure, Cours d'algèbre. Primalité Divisibilité. Codes [détail des éditions]

Ce document provient de « Algorithme de Cantor-Zassenhaus ».