Análisis probabilístico del algoritmo clásico de factorización de polinomios univariados en familias sobre cuerpos finitos // Probabilistic analisys of the classic factorization algorithm of univariated polynomials in famlilies over finite fields

GUILLERMO MATERA; MARIANA PÉREZ; MELINA PRIVITELLI

CORDOBA

Encuentro; Segundo Encuentro Argentino de Cuerpos Finitos y Temas Afines; 2019

FAMAF, Universidad Nacional de Córdoba

En esta comunicación analizamos la complejidad en promedio del algoritmo clásico de factorización aplicado a ciertas familias A de polinomios univariados con coeficientes en el cuerpo finito Fq de q elementos. Este algoritmo se basa en cuatro etapas fundamentales. Primero realiza una eliminación de factores repetidos; luego descompone este polinomio libre de cuadrados en polinomios cuyos factores irreducibles tienen todos el mismo grado (factorización en distintos grados). En el tercer paso factoriza completamente estos polinomios (factorización en grados iguales). Por último, factoriza los factores repetidos que se descartaron en el primer paso. Este algoritmo está implementado en muchos paquetes de álgebra computacional. En [1], P. Flajolet, X. Gourdon y P. Panario realizan un análisis probabilístico del mismo sobre todos los polinomios en Fq[T] de grado dado, donde demuestran que éste queda determinado por la correspondiente distribución de patrones de factorización. Sin embargo, frecuentemente los polinomios a factorizar poseen características particulares que impiden aplicar directamente estos resultados. En tal sentido, utilizando estimaciones explícitas sobre la distribución de patrones de factorización sobre las familias A consideradas (ver, [2]), obtenemos resultados sobre el comportamiento en promedio del algoritmo clásico de factorización para el caso de dichas familias, que muestran que éste tiene buen comportamiento como en el caso general.REFERENCIAS[1] P. Flajolet, X. Gourdon, D. Panario. The complete analysis of a polynomial factorization algorithm over finite fields. J. Algorithms. 40 (1): 37-81, 2001.[2] G. Matera, M. Pérez, M. Privitelli. Factorization patterns on nonlinear families of univariate polynomials over a finite field, J. Algebr. Comb. (2019), 1-51.