## 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$$.

### MSC:

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

algorithm

### Citations:

Zbl 0543.00014; Zbl 0488.12001; Zbl 0546.68022