Factoring multivariate polynomials over finite fields (Q1065867)

The author presents an algorithm for the factorization of multivariate polynomials with coefficients in a finite field which is polynomial-time in the degrees of the polynomial to be factored. This algorithm makes use of a new basis reduction algorithm for lattices over \({\mathbb{F}}_ q[Y].\) In the case of two variables the algorithm is similar to the polynomial- time algorithm for the factorization of polynomials in one variable with rational coefficients [the author, \textit{H. W. Lenstra} jun. and \textit{L. Lovász}, Math. Ann. 261, 515-534 (1982; Zbl 0488.12001] and to that given by \textit{A. L. Chistov} and \textit{D. Yu. Grigor'ev} [Prepr. LOMI E-5- 82 (1982; Zbl 0509.68029)]. If \(f\in {\mathbb{F}}_ q[X_ 1,X_ 2,...,X_ t]\) for \(t>2\) the problem is reduced to the case \(t=2\) by substituting high enough powers of \(X_ 2\) for \(X_ 3\) up to \(X_ t\).