On the degrees of irreducible factors of polynomials over a finite field (Q1297409)

Let \({\widetilde{\mathbb F}}_q[X]\) denote the multiplicative semigroup of monic polynomials in the determinate \(X\) over the finite field \({\mathbb F}_q\) with \(q\) elements. Many deterministic and probabilistic factorization algorithms require first a distinct degree factorization where the given polynomial \(f\) is first factored into polynomials \(f_d\), the product of all irreducible factors of degree \(d\). Let \(r\) be the number of such factors, termed the irreducible degree of \(f\), and \(k\) the total number of irreducible factors. The main result of the paper shows that the number \(r\) of irreducible degrees of a polynomial of degree \(n\) has a mean value of \[ \log n + \gamma + c_1 (q) - A(q) + O(1/n) \] as \(n \rightarrow \infty\), where \(\gamma\) is Euler's constant and \[ c_1 (q) = \sum_{r=1}^\infty ( \pi (r) - q^r /r) q^{-r} <0 \quad\text{and}\quad A(q) = \sum_{m=1}^\infty \left( (1-q^{-m})^{\pi (m)} -1 + {\pi (m) \over q^m} \right) \] where \(\pi (m)\) is the number of irreducible polynomials of degree \(m\) over \({\mathbb F}_q\). In addition, it is shown that almost all polynomials of degree \(n\) have approximately \(\log n\) irreducible degrees.