Generators and irreducible polynomials over finite fields

Weil's character sum estimate is used to study the problem of constructing generators for the multiplicative group of a finite field. An application to the distribution of irreducible polynomials is given, which confirms an asymptotic version of a conjecture of Hansen-Mullen.

     

Generating series for irreducible polynomials over finite fields

We count the number of irreducible polynomials in several variables of a given degree over a finite field. The results are expressed in terms of a generating series, an exact formula and an asymptotic approximation. We also consider the case of the multi-degree and the case of indecomposable polynomials.     

Fast construction of irreducible polynomials over finite fields

We present a randomized algorithm that on inputting a finite field K with q elements and a positive integer d outputs a degree d irreducible polynomial in K[x]. The running time is d ^1+?(d)×(log q)^5+?(q) elementary operations. The function ? in this expression is a real positive function belonging to the class o(1), especially, the complexity is quasi-linear in the degree d. Once given such an irreducible polynomial of degree d, we can compute random irreducible polynomials of degree d at the expense of d ^1+?(d) × (log q)^1+?(q) elementary operations only.     

Counting irreducible polynomials with prescribed coefficients over a finite field

We continue our study on counting irreducible polynomials over a finite field with prescribed coefficients. We set up a general combinatorial framework using generating functions with coefficients from a group algebra which is generated by equivalence classes of polynomials with prescribed coefficients. Simplified expressions are derived for some special cases. Our results extend some earlier results.     

A correspondence of certain irreducible polynomials over finite fields

An explicit correspondence between certain cubic irreducible polynomials over ${\mathbb{F}}_q$ and cubic irreducible polynomials of special type over ${\mathbb{F}}_{q^2}$ was established by Kim et al. In this paper, we give a generalization of their result to irreducible polynomials of odd prime degree. Our result includes the result of Kim et al. as a special case where the degree is three.     

The explicit construction of irreducible polynomials over finite fields

For a finite field GF(q) of odd prime power order q, and n 1, we construct explicitly a sequence of monic irreducible reciprocal polynomials of degree n2 ^m (m = 1, 2, 3, ...) over GF(q). It is the analog for fields of odd order of constructions of Wiedemann and of Meyn over GF(2). We also deduce iterated presentations of GF (q ⁿ 2).     

Distribution of irreducible polynomials of small degrees over finite fields

D. Wan very recently proved an asymptotic version of a conjecture of Hansen and Mullen concerning the distribution of irreducible polynomials over finite fields. In this note we prove that the conjecture is true in general by using machine calculation to verify the open cases remaining after Wan's work.

     

Counting polynomials over finite fields with prescribed leading coefficients and linear factors

We count the number of polynomials over finite fields with prescribed leading coefficients and a given number of linear factors. This is equivalent to counting codewords in Reed-Solomon codes which are at a certain distance from a received word. We first apply the generating function approach, which is recently developed by the author and collaborators, to derive expressions for the number of monic polynomials with prescribed leading coefficients and linear factors. We then apply Li and Wan's sieve formula to simplify the expressions in some special cases. Our results extend and improve some recent results by Li and Wan, and Zhou, Wang and Wang.     

Number of irreducible polynomials and pairs of relatively prime polynomials in several variables over finite fields

We discuss several enumerative results for irreducible polynomials of a given degree and pairs of relatively prime polynomials of given degrees in several variables over finite fields. Two notions of degree, the total degree and the vector degree, are considered. We show that the number of irreducibles can be computed recursively by degree and that the number of relatively prime pairs can be expressed in terms of the number of irreducibles. We also obtain asymptotic formulas for the number of irreducibles and the number of relatively prime pairs. The asymptotic formulas for the number of irreducibles generalize and improve several previous results by Carlitz, Cohen and Bodin.     

Factoring polynomials over finite fields

We propose a new deterministic method of factoring polynomials over finite fields. Assuming the generalized Riemann hypothesis (GRH), we obtain, in polynomial time, the factorization of any polynomial with a bounded number of irreducible factors. Other consequences include a polynomial time algorithm to find a nontrivial factor of any completely splitting even-degree polynomial when a quadratic nonresidue in the field is given.     

Dickson polynomials over finite fields

In this paper we introduce the notion of Dickson polynomials of the $(k+1)$-th kind over finite fields ${\mathbb{F}}_{p^m}$ and study basic properties of this family of polynomials. In particular, we study the factorization and the permutation behavior of Dickson polynomials of the third kind.     

On an iterated construction of irreducible polynomials over finite fields of even characteristic by Kyuregyan

We deal with the construction of sequences of irreducible polynomials with coefficients in finite fields of even characteristic. We rely upon a transformation used by Kyuregyan in 2002, which generalizes the Q-transform employed previously by Varshamov and Garakov (1969) as well as by Meyn (1990) for the synthesis of irreducible polynomials. While in the iterative procedure described by Kyuregyan the coefficients of the initial polynomial of the sequence have to satisfy certain hypotheses, in the present paper these conditions are removed. We construct infinite sequences of irreducible polynomials of nondecreasing degree starting from any irreducible polynomial.     

The number of irreducible polynomials over finite fields of characteristic 2 with given trace and subtrace

In this paper we obtained the formula for the number of irreducible polynomials with degree n over finite fields of characteristic two with given trace and subtrace. This formula is a generalization of the result of Cattell et al. (2003) [2].