Relatively prime polynomials and nonsingular Hankel matrices over finite fields

The probability for two monic polynomials of a positive degree n with coefficients in the finite field Fq to be relatively prime turns out to be identical with the probability for an n×n Hankel matrix over Fq to be nonsingular. Motivated by this, we give an explicit map from pairs of coprime polynomials to nonsingular Hankel matrices that explains this connection. A basic tool used here is the classical notion of Bezoutian of two polynomials. Moreover, we give simpler and direct proofs of the general formulae for the number of m-tuples of relatively prime polynomials over Fq of given degrees and for the number of n×n Hankel matrices over Fq of a given rank.     

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.     

Counting irreducible polynomials over finite fields

In this paper we generalize the method used to prove the Prime Number Theorem to deal with finite fields, and prove the following theorem:

On coefficients of polynomials over finite fields

In this paper we study the relation between coefficients of a polynomial over finite field Fq and the moved elements by the mapping that induces the polynomial. The relation is established by a special system of linear equations. Using this relation we give the lower bound on the number of nonzero coefficients of polynomial that depends on the number m of moved elements. Moreover we show that there exist permutation polynomials of special form that achieve this bound when m|q−1. In the other direction, we show that if the number of moved elements is small then there is an recurrence relation among these coefficients. Using these recurrence relations, we improve the lower bound of nonzero coefficients when m?q−1 and . As a byproduct, we show that the moved elements must satisfy certain polynomial equations if the mapping induces a polynomial such that there are only two nonzero coefficients out of 2m consecutive coefficients. Finally we provide an algorithm to compute the coefficients of the polynomial induced by a given mapping with O(q3/2) operations.     

Irreducible compositions of polynomials over finite fields

The paper is devoted to the composition method of constructing families of irreducible polynomials over finite fields.     

Subquadratic-time factoring of polynomials over finite fields

New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree over a finite field of constant cardinality in time . Previous algorithms required time . The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree over the finite field with elements, the algorithms use arithmetic operations in .

The new ``baby step/giant step' techniques used in our algorithms also yield new fast practical algorithms at super-quadratic asymptotic running time, and subquadratic-time methods for manipulating normal bases of finite fields.

     

Testing low‐degree polynomials over prime fields

We present an efficient randomized algorithm to test if a given function f : ?? → ??_p (where p is a prime) is a low‐degree polynomial. This gives a local test for Generalized Reed‐Muller codes over prime fields. For a given integer t and a given real ε > 0, the algorithm queries f at O( ) points to determine whether f can be described by a polynomial of degree at most t. If f is indeed a polynomial of degree at most t, our algorithm always accepts, and if f has a relative distance at least ε from every degree t polynomial, then our algorithm rejects f with probability at least . Our result is almost optimal since any such algorithm must query f on at least points. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On evaluating multivariate polynomials over finite fields

Some evaluation methods of multivariate polynomials over finite fields are described and their multiplicative complexity is discussed.     

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.

     

Irreducible polynomials over finite fields. I

A function H_n(a₁, a₂, a₃) is found, computing the number of normalized irreducible polynomials of degree n over a finite field F_q, with the first three coefficients a₁, a₂, and a₃ fixed for n = 4. The function is expressed via some sums of characters admitting “good” estimates. In particular, the following theorem is proved: If q = 3m + 1, a ∈ k^*, and N (a) = H₄(0, 0, a), then $$N(a) = \frac{1}{4}(q - 2\operatorname{Re} [(\lambda (a) - \eta ( - 1)\bar \lambda (a/2))J(\lambda ,\lambda )] - \eta ( - 1)),$$ where η is a quadratic character of the field k = F_q, λ is a nontrivial cubic character, and J(λ, λ) is the known Jacobi sum.     

Central polynomials for matrices over finite fields

Let c(x ₁,?…?,?x _d ) be a multihomogeneous central polynomial for the n?×?n matrix algebra M _n (K) over an infinite field K of positive characteristic p. We show that there exists a multihomogeneous polynomial c ₀(x ₁,?…?,?x _d ) of the same degree and with coefficients in the prime field 𝔽 _p which is central for the algebra M _n (F) for any (possibly finite) field F of characteristic p. The proof is elementary and uses standard combinatorial techniques only.