TY - JOUR
T1 - A generalized counting and factoring method for polynomials over finite fields
AU - Mullin, Ronald C.
AU - Yucas, Joseph L.
AU - Mullen, Gary L.
PY - 2010/2
Y1 - 2010/2
N2 - We discuss a transform on the set of rational functions over the finite field Fq. For a subclass of these functions, the transform yields a polynomial and its factorization as a product of the set of monic irreducible polynomials all of which share a common property P that depends on the choice of rational function. A general formula is derived from the factorization for the number of monic irreducible polynomials of degree n having property P. However it is also possible in some instances to exploit the properties of the factorization to obtain a "closed" form of the answer more directly. We illustrate the method with four examples, two of which appear in the literature. In particular, we give alternative proofs for a result of L. Carlitz on the number of monic irreducible self-reciprocal polynomials and a remarkable result of S. D. Cohen on the number of (r,m)-polynomials, that is, monic irreducible polynomials of the form f(xr) of degree mr. We also give a generalization of the factorization of xq-1 -1 over Fq that includes the factorization of x(q-1)2 -1. The new results concern translation invariant polynomials, which lead to a consideration of the orders of elements in Fq, the algebraic closure of F q. We show that there are an infinite number of θ ε F̄q such that ord(θ) and ord(r(θ)) are related, in the sense that given one, one can infer information about the other.
AB - We discuss a transform on the set of rational functions over the finite field Fq. For a subclass of these functions, the transform yields a polynomial and its factorization as a product of the set of monic irreducible polynomials all of which share a common property P that depends on the choice of rational function. A general formula is derived from the factorization for the number of monic irreducible polynomials of degree n having property P. However it is also possible in some instances to exploit the properties of the factorization to obtain a "closed" form of the answer more directly. We illustrate the method with four examples, two of which appear in the literature. In particular, we give alternative proofs for a result of L. Carlitz on the number of monic irreducible self-reciprocal polynomials and a remarkable result of S. D. Cohen on the number of (r,m)-polynomials, that is, monic irreducible polynomials of the form f(xr) of degree mr. We also give a generalization of the factorization of xq-1 -1 over Fq that includes the factorization of x(q-1)2 -1. The new results concern translation invariant polynomials, which lead to a consideration of the orders of elements in Fq, the algebraic closure of F q. We show that there are an infinite number of θ ε F̄q such that ord(θ) and ord(r(θ)) are related, in the sense that given one, one can infer information about the other.
UR - http://www.scopus.com/inward/record.url?scp=78651528093&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78651528093&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:78651528093
SN - 0835-3026
VL - 72
SP - 121
EP - 143
JO - Journal of Combinatorial Mathematics and Combinatorial Computing
JF - Journal of Combinatorial Mathematics and Combinatorial Computing
ER -