Counting Reducible, Powerful, and Relatively Irreducible Multivariate Polynomials over Finite Fields
Joachim von zur Gathen, Alfredo Viola, Konstantin Ziegler · SIAM Journal on Discrete Mathematics · 2013
We present counting methods for some special classes 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.