Factoring Multivariate Polynomials over Finite Fields

摘要

An algorithm for the factorization of multivariate polynomials with coefficients in a finite field is given. The algorithm is polynomial-time in the degrees of the polynomial to be factored. A reduction algorithm for lattices over the polynomials, with coefficients in the finite field containing q elements, q power of some prime p, is used. The technique is to reduce the polynomial to one in two variables only by substituting powers of one variable into the others, and then working module the principal ideal generated by the powers of an irreducible polynomial in one variable.