Factorizando polinomios de bajo grado

8

¿Cuál es el algoritmo más rápido conocido para factorizar polinomios con n variables y grado total d ? Aquí, n está creciendo d está arreglado. La mayoría del trabajo parece considerar el caso cuando d está creciendo n es fijo. Me interesan los resultados tanto en campos finitos como en racionales.

arnab
fuente

Respuestas:

8

Sea K un campo de la característica 0 o al menos d(d1)+1 , y pK[x1,,xn] sea ​​un polinomio de grado total como máximo d . Si d es fijo n está creciendo, uno tiene los siguientes límites de complejidad para la reducción de la factorización de p a la factorización de un polinomio univariado de grado d : (La notación O~() ignora los factores logarítmicos).

  1. Algoritmos deterministas:

    • O~((n+dn)4) operaciones de campo, utilizando algoritmos de multiplicación ingenuos;
    • 2<ω3O~((n+2d2n1)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
  2. 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

Bruno
fuente
¡Muchas gracias! ¿Conoces algún trabajo sobre campos muy pequeños, por ejemplo, GF (2)?
arnab
3
El límite que menciono en mi respuesta viene dado por algoritmos que reducen la factorización multivariada a factorización univariada. AFAIK, los límites más conocidos cuando los resultados anteriores no se aplican (es decir, cuando la característica es demasiado pequeña) están dados por algoritmos que hacen una reducción multivariada → bivariada → univariada. Para más información sobre esto, puede echar un vistazo a Factorización de polinomios multivariados por Kaltofen y Lecerf, capítulo 11.5 del Manual de campos finitos . Una versión preliminar de este capítulo está aquí .
Bruno