On the degrees of irreducible factors of polynomials over a finite field
type: Item
instance of: scholarly article
title: On the degrees of irreducible factors of polynomials over a finite field
zbMATH Open document ID: 0931.11055
DOI: 10.1016/S0012-365X(98)00174-5
author: Arnold Knopfmacher
published in: Discrete Mathematics
publication date: 1999-11-10T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 11T06
zbMATH DE Number: 1321775
zbMATH Keywords: polynomials over a finite field
zbMATH Keywords: irreducible polynomials
reviewed by: Ian Blake
MaRDI profile type: Publication
cites work: Factoring polynomials using fewer random bits
cites work: A New Algorithm for Factoring Polynomials Over Finite Fields
cites work: Q4226693
cites work: Singularity Analysis of Generating Functions
cites work: Gaussian limiting distributions for the number of components in combinatorial structures
cites work: Computing Frobenius maps and factoring polynomials
cites work: Counting irreducible factors of polynomials over a finite field
cites work: Distinct Degree Factorizations for Polynomials over a Finite Field
cites work: Q3935355
cites work: On the deterministic complexity of factoring polynomials over finite fields
cites work: Q4886127
cites work: Three problems in combinatorial asymptotics
Recommended article: On the number of irreducible factors of a polynomial over a finite field
Recommended article: ON IRREDUCIBLE FACTORS OF POLYNOMIALS OVER COMPLETE FIELDS
Recommended article: On the degrees of polynomial divisors over finite fields
Recommended article: On the degrees of irreducible factors of a polynomial
Recommended article: On the number of factorizations of polynomials over finite fields
Recommended article: Q3353129
Recommended article: Counting irreducible factors of polynomials over a finite field
Recommended article: Distinct Degree Factorizations for Polynomials over a Finite Field
Recommended article: On the distribution of polynomials having a given number of irreducible factors over finite fields
Recommended article: Polynomials over finite fields free from large and small degree irreducible factors
description: scientific article; zbMATH DE number 1321775