Algoritmo de Berlekamp–Zassenhaus - Enciclopedia

En matemáticas, en particular en álgebra computacional, el algoritmo de Berlekamp–Zassenhaus es un algoritmo para factorizar polinomios sobre los enteros, nombrado en honor de Elwyn Berlekamp y Hans Zassenhaus. Como consecuencia del lema de Gauss, esto equivaldría a resolver el problema también sobre los racionales.
El algoritmo comienza encontrando factorizaciones sobre campos finitos adecuados utilizando el lema de Hensel para elevar la solución desde módulo un primo p a una potencia conveniente de p. Después de esto, se encuentran los factores derechos como un subconjunto de estos.
El caso peor de este algoritmo es exponencial en el número de factores.
Van Hoeij (2002) mejoró este algoritmo utilizando el algoritmo LLL, reduciendo sustancialmente el tiempo necesario para elegir los subconjuntos adecuados de factores módulo p.


Véase también
Algoritmo de Berlekamp


Referencias
Berlekamp, E. R. (1967), "Factoring polynomials over finite fields", Bell System Technical Journal, 46 (8): 1853–1859, doi:10.1002/j.1538-7305.1967.tb03174.x, MR 0219231.
Berlekamp, E. R. (1970), "Factoring polynomials over large finite fields", Mathematics of Computation, 24 (111): 713–735, doi:10.2307/2004849, JSTOR 2004849, MR 0276200.
Cantor, David G.; Zassenhaus, Hans (1981), "A new algorithm for factoring polynomials over finite fields", Mathematics of Computation, 36 (154): 587–592, doi:10.2307/2007663, JSTOR 2007663, MR 0606517.
Geddes, K. O.; Czapor, S. R.; Labahn, G. (1992), Algorithms for computer algebra, Boston, MA: Kluwer Academic Publishers, Bibcode:1992afca.book.....G, doi:10.1007/b102438, ISBN 0-7923-9259-0, MR 1256483.
Van Hoeij, Mark (2002), "Factoring polynomials and the knapsack problem", Journal of Number Theory, 95 (2): 167–189, doi:10.1016/S0022-314X(01)92763-5, MR 1924096.
Zassenhaus, Hans (1969), "On Hensel factorization. I", Journal of Number Theory, 1 (3): 291–311, Bibcode:1969JNT.....1..291Z, doi:10.1016/0022-314X(69)90047-X, MR 0242793.


Enlaces externos
Domazet, Haris. "Algoritmo de Berlekamp-Zassenhaus". MathWorld.