Abstract
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 sth power of a nonconstant polynomial), and the relatively irreducible ones (irreducible but reducible over an extension field). One approach employs generating functions, another one a combinatorial method. They yield approximations with relative errors that essentially decrease exponentially in the input size.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bodin, A.: Number of irreducible polynomials in several variables over finite fields. American Mathematical Monthly 115(7), 653–660 (2008)
Bodin, A.: Generating series for irreducible polynomials over finite fields (2009), http://arxiv.org/abs/0910.1680v2 (Accessed December 10, 2009)
Carlitz, L.: The distribution of irreducible polynomials in several indeterminates. Illinois Journal of Mathematics 7, 371–375 (1963)
Carlitz, L.: The distribution of irreducible polynomials in several indeterminates II. Canadian Journal of Mathematics 17, 261–266 (1965)
Cohen, S.: The distribution of irreducible polynomials in several indeterminates over a finite field. Proceedings of the Edinburgh Mathematical Society 16, 1–17 (1968)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
Gao, S., Lauder, A.G.B.: Hensel Lifting and Bivariate Polynomial Factorisation over Finite Fields. Mathematics of Computation 71(240), 1663–1676 (2002)
von zur Gathen, J.: Counting reducible and singular bivariate polynomials. Finite Fields and Their Applications 14(4), 944–978 (2008) http://dx.doi.org/10.1016/j.ffa.2008.05.005 ; Extended abstract in Proceedings of the, International Symposium on Symbolic and Algebraic Computation ISSAC 2007, Waterloo, Ontario, Canada, pp. 369-376 (2008)
von zur Gathen, J., Viola, A., Ziegler, K.: Counting reducible, powerful, and relatively irreducible multivariate polynomials over finite fields (2009), http://arxiv.org/abs/0912.3312
Hou, X.-D., Mullen, G.L.: Number of Irreducible Polynomials and Pairs of Relatively Prime Polynomials in Several Variables over Finite Fields. Finite Fields and Their Applications 15(3), 304–331 (2009), http://dx.doi.org/10.1016/j.ffa.2008.12.004
Wan, D.: Zeta Functions of Algebraic Cycles over Finite Fields. Manuscripta Mathematica 74, 413–444 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
von zur Gathen, J., Viola, A., Ziegler, K. (2010). Counting Reducible, Powerful, and Relatively Irreducible Multivariate Polynomials over Finite Fields. In: López-Ortiz, A. (eds) LATIN 2010: Theoretical Informatics. LATIN 2010. Lecture Notes in Computer Science, vol 6034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12200-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-12200-2_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12199-9
Online ISBN: 978-3-642-12200-2
eBook Packages: Computer ScienceComputer Science (R0)