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 Cantor 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 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 Xqn-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 Xq-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 Xq2-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 \mathbb{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 f1, jusqu'à fr 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 fi sera notée ai pour chaque i, tel que tous les ai valent 0, 1, ou -1, et tel que deux au moins des ensembles suivants sont non vides :

A = {i | ai(x) = 0},
B = {i | ai(x) = − 1},
C = {i | ai(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 qd, 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 ai 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]


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Cantor-Zassenhaus de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • Algorithme De Berlekamp — L algorithme de Berlekamp est une méthode de factorisation des polynômes à coefficients dans un corps fini, qui repose sur des calculs de PGCD de polynômes et des opérations matricielles. Il a été découvert par Elwyn Berlekamp en 1967, et est… …   Wikipédia en Français

  • Algorithme de berlekamp — L algorithme de Berlekamp est une méthode de factorisation des polynômes à coefficients dans un corps fini, qui repose sur des calculs de PGCD de polynômes et des opérations matricielles. Il a été découvert par Elwyn Berlekamp en 1967, et est… …   Wikipédia en Français

  • Algorithme de van Hoeij — En mathématiques et en algorithmique, les algorithmes de van Hoeij sont des algorithmes efficaces de factorisation des polynômes à coefficients rationnels, ou plus généralement à coefficients dans un corps de nombres ou de fonctions. Ils datent… …   Wikipédia en Français

  • Algorithme de Berlekamp — L algorithme de Berlekamp est une méthode de factorisation des polynômes à coefficients dans un corps fini, qui repose sur des calculs de PGCD de polynômes et des opérations matricielles. Il a été découvert par Elwyn Berlekamp en 1967, et est… …   Wikipédia en Français

  • Hans Julius Zassenhaus — en 1987 Hans Julius Zassenhaus (né le 28 mai 1912 à Coblence, mort le 21 novembre 1991 à Columbus, dans l’Ohio, aux États Unis) est un …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Liste Des Algorithmes — Sommaire 1 Liste par catégories 1.1 Compression de données 1.2 Tri 1.2.1 Algorithmes en temps quadratique …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”