von zur Gathen, Joachim; Viola, Alfredo; Ziegler, Konstantin Counting reducible, powerful, and relatively irreducible multivariate polynomials over finite fields. (English) Zbl 1348.11094 SIAM J. Discrete Math. 27, No. 2, 855-891 (2013). 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. Reviewer: Astrid Reifegerste (Magdeburg) Cited in 1 ReviewCited in 5 Documents MSC: 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 Keywords:multivariate polynomials; finite fields; combinatorics on polynomials; counting problems; generating functions; analytic combinatorics PDF BibTeX XML Cite \textit{J. von zur Gathen} et al., SIAM J. Discrete Math. 27, No. 2, 855--891 (2013; Zbl 1348.11094) Full Text: DOI arXiv