zbMATH — the first resource for mathematics

Counting reducible, powerful, and relatively irreducible multivariate polynomials over finite fields. (English) Zbl 1348.11094
Authors’ abstract: We present counting methods for some special cases of multivariate polynomials over a finite field, namely, the reducible ones, the \(s\)-powerful ones (divisible by the \(s\)th power of a nonconstant polynomial), and the relatively irreducible ones (irreducible but reducible over an extension field). One approach employs generating functions, and another one uses a combinatorial method. They yield exact formulas and approximations with relative errors that essentially decrease exponentially in the input size.

11T06 Polynomials over finite fields
12E20 Finite fields (field-theoretic aspects)
12Y05 Computational aspects of field theory and polynomials (MSC2010)
05A15 Exact enumeration problems, generating functions
Full Text: DOI arXiv