Un algorithme aléatoire de factorisation de polynômes sur corps finis, généralement exécuté en deux phases : factorisation par degrés distincts suivie de la séparation des facteurs de degré égal à l'aide de polynômes aléatoires et d'exponentiations dans le groupe multiplicatif pour séparer les facteurs avec forte probabilité.

Principe

Utiliser l'échantillonnage probabiliste dans l'anneau quotient et l'exponentiation d'éléments de groupe : choisir un polynôme aléatoire a(x), calculer a(x)^{(q^d−1)/2} modulo f (ou des tests de groupe analogues) et prendre des pgcd avec f pour séparer des facteurs de degré d avec probabilité constante ; itérer jusqu'à la factorisation complète.

Démonstration

Une fois que la factorisation par degrés distincts fournit un produit de facteurs dont les composantes irréductibles ont toutes le degré d, choisir des polynômes aléatoires a(x) et calculer pgcd(a^{(q^d-1)/2}-1, f) ; un choix aléatoire sépare le facteur en deux facteurs non triviaux avec une probabilité de succès constante en espérance, nécessitant peu d'essais.

Mauvaise application

Négliger la prétraitement sans facteurs multiples ou la séparation par degré distinct avant d'essayer la séparation par degré égal dégrade les probabilités de succès et peut produire des séparations erronées ; supposer le succès en un seul essai conduit à un mauvais comportement dans le pire cas étant donné la nature probabiliste.

Conséquence

Cantor–Zassenhaus fournit un algorithme à temps d'exécution espéré favorable et à faible surcharge mémoire pour la factorisation sur corps finis, et il s'adapte bien en pratique à de grands corps et degrés ; sa nature aléatoire le rend rapide et simple à implémenter.

Inversion

Contrarié par des approches déterministes d'algèbre linéaire (Berlekamp) ou par des algorithmes modulaires déterministes : alors que Cantor–Zassenhaus échange le déterminisme contre la vitesse, la réversion obtient le déterminisme au prix de calculs linéaires plus lourds ou d'algorithmes plus complexes.

Limite

S'applique aux polynômes sur corps finis et suppose une arithmétique de corps accessible ; ses garanties probabilistes sont asymptotiques et dépendent de la taille du corps et du degré — sur des corps très petits ou des polynômes structurés, des précautions supplémentaires ou plusieurs essais sont nécessaires.

Tension sémantique

Il existe une tension pratique entre la séparation aléatoire (bon comportement moyen, structure plus simple) et les algorithmes déterministes (comportement garanti mais ressources souvent plus lourdes) ; Cantor–Zassenhaus est souvent préféré en pratique pour sa simplicité et sa rapidité.

Synthèse

Cantor–Zassenhaus est une méthode de factorisation aléatoire en deux étapes qui segmente d'abord par degré puis sépare les composantes de degré égal par échantillonnage aléatoire et exponentiation de groupe : elle atteint une factorisation polynomiale efficace en temps attendu sur corps finis grâce à la séparation probabiliste et aux pgcd répétés.