Un algoritmo aleatorizado para factorizar polinomios sobre cuerpos finitos, típicamente ejecutado en dos fases: factorización por grado distinto seguida de separación de grado igual usando polinomios aleatorios y exponenciación en el grupo multiplicativo para separar factores con alta probabilidad.

Principio

Usar muestreo probabilístico en el anillo cociente y exponenciación grupal: escoger a(x) al azar, calcular a(x)^{(q^d−1)/2} módulo f (o pruebas de grupo análogas) y tomar mcd con f para separar factores de grado d con probabilidad constante; iterar hasta la factorización completa.

Demostración

Tras obtener por factorización por grados distintos un producto cuyas componentes irreducibles tienen todas grado d, elegir polinomios aleatorios a(x) y calcular mcd(a^{(q^d-1)/2}-1, f); una elección aleatoria separa el factor en dos no triviales con probabilidad constante esperada, por lo que bastan pocos intentos.

Aplicación incorrecta

Omitir el preprocesamiento de sin factores múltiples o la separación por grados distintos antes de intentar la separación por grados iguales degrada las probabilidades de éxito y puede producir divisiones de factores incorrectas; asumir éxito en un único intento conduce a pobre comportamiento en el peor caso por la naturaleza probabilística.

Consecuencia

Cantor–Zassenhaus ofrece un algoritmo con buen tiempo de ejecución esperado y bajo coste de memoria para factorizar sobre cuerpos finitos, y escala bien en la práctica para campos y grados grandes; su naturaleza aleatoria lo hace rápido y sencillo de implementar.

Inversión

Revertido por enfoques deterministas de álgebra lineal (Berlekamp) o por algoritmos modulares deterministas: mientras Cantor–Zassenhaus intercambia determinismo por velocidad, la reversión proporciona determinismo a costa de mayor trabajo lineal-algebraico o algoritmos más complejos.

Límite

Se aplica a polinomios sobre cuerpos finitos y asume aritmética de campo accesible; sus garantías probabilísticas son asintóticas y dependen del tamaño del campo y del grado—en campos muy pequeños o con polinomios estructurados se requieren precauciones adicionales o múltiples intentos.

Tensión semántica

Existe tensión práctica entre el splitting aleatorio (rápido en el caso promedio, estructura más simple) y algoritmos deterministas (comportamiento garantizado pero a menudo más costosos en recursos); Cantor–Zassenhaus suele preferirse por su simplicidad y velocidad.

Síntesis

Cantor–Zassenhaus es un método aleatorizado en dos etapas que primero separa por grado y luego divide componentes de igual grado mediante muestreo aleatorio y exponenciación en el grupo: consigue factoración polinómica eficiente en tiempo esperado sobre cuerpos finitos mediante separaciones probabilísticas y mcd repetidos.