Factorization of univariate integer polynomials by diophantine approximation and an improved basis reduction algorithm. (English) Zbl 0569.68030

Automata, languages and programming, 11th Colloq., Antwerp/Belg. 1984, Lect. Notes Comput. Sci. 172, 436-447 (1984).
[For the entire collection see Zbl 0543.00014.]
We describe an algorithm for factoring univariate integer polynomials f (except for their integer prime factors) with a running time of \(O(n^{6+\epsilon}+n^ 4(\log | f|)^{2+\epsilon})\) bit operations (for any \(\epsilon >0)\), where n denotes the degree, and \(| f|\) is the norm of f. With classical integer multiplication the bound is \(O(n^ 8+n^ 5(\log | f|)^ 3)\), respectively. This improves the corresponding bounds of A. K. Lenstra, H. W. Lenstra jun. and L. Lovász [Math. Ann. 261, 515-534 (1982; Zbl 0488.12001)] plus E. Kaltofen’s refinement [Lect. Notes Comput. Sci. 162, 236-244 (1983; Zbl 0546.68022)] by a factor of order \(n^ 3\).


68W30 Symbolic computation and algebraic computation
68Q25 Analysis of algorithms and problem complexity
12D05 Polynomials in real and complex fields: factorization