Sea K un campo de la característica 0 0 o al menos re( d- 1 ) + 1 , y p ∈ K [ x1, ... , xnorte] sea un polinomio de grado total como máximo re . Si re es fijo norte está creciendo, uno tiene los siguientes límites de complejidad para la reducción de la factorización de pags a la factorización de un polinomio univariado de grado re : (La notación O~( ⋅ ) ignora los factores logarítmicos).
Algoritmos deterministas:
- O~((n+dn)4) operaciones de campo, utilizando algoritmos de multiplicación ingenuos;
- 2<ω≤3O~((n+2d−2n−1)dω) operaciones de campo, si los algoritmos de multiplicación rápida están disponibles, donde es un exponente admisible para el álgebra lineal.2<ω≤3
Algoritmos probabilísticos:
- O~((n+dn)) operaciones de campo, si hay disponibles algoritmos de multiplicación rápida.
Entonces, uno tiene que factorizar un polinomio univariado de grado . La complejidad de este paso ya no depende de , por lo que los límites anteriores siguen siendo válidos para los algoritmos completos de factorización. La única diferencia está en la característica positiva: dado que no se sabe que un algoritmo determinista de tiempo polinómico factorice un polinomio univariado, incluso la reducción determinista produce un algoritmo probabilístico. No obstante, si es realmente fijo y pequeño, se puede reemplazar el algoritmo probabilístico de tiempo polinómico por uno determinista de tiempo exponencial.n ddnd
Tenga en cuenta que el límite probabilístico es óptimo hasta los factores logarítmicos ya que es el tamaño de entrada.(n+dO~((n+dn))(n+dn)
Se pueden encontrar más detalles en el documento Algoritmos de factorización polinomiales multivariados densos y mejorados de Grégoire Lecerf ( enlace sin paywall ).
Otra referencia, especialmente para campos de características pequeñas, es EL Kaltofen & G. Lecerf, Factorización de polinomios multivariados ( enlace sin paywall ), capítulo 11.5 de GL Mullen y D. Panario, editores, Manual de campos finitos .
¹ El resultado debe suponer que .ω>2