On the number of irreducible factors of degree k dividing a given polynomial over GF(q)
type: Item
instance of: scholarly article
title: On the number of irreducible factors of degree k dividing a given polynomial over GF(q)
zbMATH Open document ID: 0703.11071
DOI: 10.1007/BF01277062
published in: Archiv der Mathematik
publication date: 1989-01-01T00:00:00Z
review text: This paper gives a nice approach to the problem of counting the number of irreducible factors of degree k dividing a given polynomial f(x) over GF(q) namely this number is \[ (\sum_{i| k}\mu (k/i)\quad \dim (\ker n(\pi^ i-id)))/\phi (k), \] where \(\pi\) is the Frobenius automorphism of \(R=GF(q)[x]/f(x)GF(q)[x]\) defined by \(\pi\) (class \((g))=class\) \(g^ q\) (in the factor ring). There are two major steps, the first one is to establish that the counting formula \[ \sum^{n}_{\ell =1}\gcd (k,\ell)A(f,\ell)=\dim (\ker n(\pi^ k-id)) \] where A(f,\(\ell)\) is the number of irreducible polynomials of degree \(\ell\) dividing f (Schwarz formula) is a consequence of the formula \(\sum \gcd (k,\ell)a(\pi,\ell)=\) number of all cycles of \(\pi\) where \(\pi\) denotes a permutation \(\pi \in S_ n\) and a(\(\pi\),\(\ell)\) the number of cycles of length \(\ell\) of \(\pi\). This is a consequence of the \(\pi\)- module structure of R [cf. \textit{H. Lüneburg}, On the rational normal form of endomorphisms (1987; Zbl 0635.12012)]. Finally using Schwarz formula and Möbius inversion formula (compared with the other methods which require to compute the inverse of the matrix \(S=(\gcd (i,j)))\) the final result is obtained.
Mathematics Subject Classification ID: 11T06
zbMATH DE Number: 4152518
zbMATH Keywords: irreducible polynomials
zbMATH Keywords: Schwarz formula
zbMATH Keywords: Möbius inversion formula
author: Heinz Lüneburg
MaRDI profile type: Publication
cites work: On Polynomial Factorization Over Finite Fields
cites work: ON THE REDUCTIBILITY OF POLYNOMIALS OVER A FINITE FIELD
Recommended article: Q5330664
Recommended article: Factoring modular polynomials
Recommended article: A Deterministic Algorithm for Factorizing Polynomials over Extensions GF(pm) of GF(p), p a Small Prime
Recommended article: Finding the number of factors of a polynomial
Recommended article: Q3772322
Recommended article: On polynomial factorization
Recommended article: Q3735804
Recommended article: Factoring polynomials of the form \(f(x^n) \in \mathbb{F}_q [x]\)
Recommended article: Factorizations of root-based polynomial compositions
Recommended article: On the degrees of irreducible factors of polynomials over a finite field
description: scientific article; zbMATH DE number 4152518