Factorization of Q(h(T)(x)) over a finite field where Q(x) is irreducible and h(T)(x) is linear—I

Let GF(q) be the finite field of order q, let Q(x) be an irreducible polynomial in GF(q)(x), and let h(T)(x) be a linear polynomial in GF(q)[x], where T:x→x^q. We use properties of the linear operator h(T) to give conditions for Q(h(T)(x)) to have a root of arbitrary degree k over GF(q), and we describe how to count the irreducible factors of Q(h(T)(x)) of degree k over GF(q). In addition we compare our results with those Ore which count the number of irreducible factors belonging to a linear polynomial having index k.     

On the classification of semifield flocks

A classical lemma of Weil is used to characterise quadratic polynomials f with coefficients GF(qⁿ), q odd, with the property that f(x) is a non-zero square for all x∈GF(q). This characterisation is used to prove the main theorem which states that there are no subplanes of order q contained in the set of internal points of a conic in PG(2,qⁿ) for q?4n²−8n+2. As a corollary to this theorem it then follows that the only semifield flocks of the quadratic cone of PG(3,qⁿ) for those q exceeding this bound are the linear flocks and the Kantor-Knuth semifield flocks.     

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).     

On hardware and software implementation of arithmetic in finite fields of characteristic 7 for calculation of pairings

We study scheme (hardware) and program (software) methods of multiplication of polynomials over fields of characteristic 7 in order to apply them to pairing-based cryptographic protocols on hyperelliptic curves of genus three. We consider hardware and software implementations of arithmetic in GF(7), GF(7²), GF(7 ⁿ ), GF(7⁷ⁿ ), and GF(7¹⁴ⁿ ) and estimate the complexity of corresponding schemes and programs.     

Enumeration of matrices of given rank with submatrices of given rank

The authors determine the number of (n+m)×t matrices A¹ of rank r+v, over a finite field GF(q), whose last m rows are those of a given matrix A of rank r+v over GF(q) and whose first n rows have a given rank u.     

On explicit factors of cyclotomic polynomials over finite fields

We study the explicit factorization of 2 ⁿ r-th cyclotomic polynomials over finite field \mathbbF_q{\mathbb{F}_q} where q, r are odd with (r, q) = 1. We show that all irreducible factors of 2 ⁿ r-th cyclotomic polynomials can be obtained easily from irreducible factors of cyclotomic polynomials of small orders. In particular, we obtain the explicit factorization of 2 ⁿ 5-th cyclotomic polynomials over finite fields and construct several classes of irreducible polynomials of degree 2 ^n–2 with fewer than 5 terms.     

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.     

On simple modules of Hecke algebras of type Dn

This is a continuation of our previous work. We classify all the simple ?_q(D _n )-modules via an automorphismh defined on the set { λ | D^λ ≠ 0}. Whenf _n(q) ≠ 0, this yields a classification of all the simple ? ^q (D _n)- modules for arbitrary n. In general ( i. e., q arbitrary), if λ⁽¹⁾ = λ⁽²⁾,wegivea necessary and sufficient condition ( in terms of some polynomials ) to ensure that the irreducible ?_q,1(B _n )- module D^λ remains irreducible on restriction to ?_q(D _n ).     

Recursive constructions of -polynomials over

This paper presents procedures for constructing irreducible polynomials over GF(2^s) with linearly independent roots (or normal polynomials or N-polynomials). For a suitably chosen initial N-polynomial F₀(x)GF(2^s) of degree n, polynomials F_k(x)GF(2^s) of degrees n2^k are constructed by iteratively applying the transformation x→x+x^-1, and their roots are shown to form a normal basis of GF(2^sn2k) over GF(2^s). In addition, the sequences are shown to be trace compatible, i.e., the trace map T_{GF(2^sn2k+1)/GF(2^sn2k)} fromGF(2^sn2k+1) onto GF(2^sn2k) maps the roots of F_k+1(x) onto those of F_k(x).     

Factorization of Q(h(T)(x)) over a finite field,where Q(x) is irreducible and h(T)(x) is linear II

Let GF(q) be the finite field of order q, let Q(x) be an irreducible polynomial in GF(qⁱ)[x], and let H(x) = h(T)(x) be a linear polynomial in GF(q)[x]. We give the degrees of the irreducible factors of Q(H(x)) in GF(qⁱ)[x], and the number of irreducible factors of each degree. We consider the special cases when H(x) is a trace function, and when h(x) is cyclotomic. Finally, we give several examples.     

On the reducibility of some composite polynomials over finite fields

Let g(x)?=?x ⁿ ?+?a _n-1 x ^n-1?+?. . .?+?a ₀ be an irreducible polynomial over ${\mathbb{F}_q}$ . Varshamov proved that for a?=?1 the composite polynomial g(x ^p ?ax?b) is irreducible over ${\mathbb{F}_q}$ if and only if ${{\rm Tr}_{\mathbb{F}_q/\mathbb{F}_p}(nb-a_{n-1})\neq 0}$ . In this paper, we explicitly determine the factorization of the composite polynomial for the case a?=?1 and ${{\rm Tr}_{\mathbb{F}_q/\mathbb{F}_p}(nb-a_{n-1})= 0}$ and for the case a?≠ 0, 1. A recursive construction of irreducible polynomials basing on this composition and a construction with the form ${g(x^{r^kp}-x^{r^k})}$ are also presented. Moreover, Cohen’s method of composing irreducible polynomials and linear fractions are considered, and we show a large number of irreducible polynomials can be obtained from a given irreducible polynomial of degree n provided that gcd(n, q ³ ? q)?=?1.     

On arithmetical algorithms over finite fields

Standard methods for calculating over GF(pⁿ), the finite field of pⁿ elements, require an irreducible polynomial of degree n with coefficients in GF(p). Such a polynomial is usually obtained by choosing it randomly and then verifying that it is irreducible, using a probabilistic algorithm. If it is not, the procedure is repeated. Here we given an explicit basis, with multiplication table, for the fields GF(p^pk), for k = 0, 1, 2,…, and their union. This leads to efficient computational methods, not requiring the preliminary calculation of irreducible polynomials over finite fields and, at the same time, yields a simple recursive formula for irreducible polynomials which generate the fields. The fast Fourier transform (FFT) is a method for efficiently evaluating (or interpolating) a polynomial of degree < n at all of the nth roots of unity, i.e., on the finite multiplicate subgroups of F, in O(nlogn) operations in the underlying field. We give an analogue of the fast Fourier transform which efficiently evaluates a polynomial on some of the additive subgroups ofF. This yields new “fast” algorithms for polynomial computation.     

Representations of finite special linear groups in non-defining characteristic

We classify irreducible modules over the finite special linear group SLn(q) in the non-defining characteristic ?, describe restrictions of irreducible modules from GLn(q) to SLn(q), classify complex irreducible characters of SLn(q) irreducible modulo l, and discuss unitriangularity of the l-decomposition matrix for SLn(q).     

Quadratic Double Circulant Codes over Fields

A generalization of the Pless symmetry codes to different fields is presented. In particular new infinite families of self-dual codes over GF(4), GF(5), GF(7), and GF(9) are introduced. It is proven that the automorphism group of some of these codes contains the group PSL₂(q). New codes over GF(4) and GF(5), with better minimum weight than previously known codes, are given.     

A four-dimensional Kerdock set over GF(3)

If m is an even integer and K = GF(q) is a field of characteristic 2, then there exists a set of q^m?1 alternating bilinear forms of degree m over K such that the difference of any two of the forms is nonsingular. Do such sets exist over fields of odd characteristic? This note constructs such a set in the smallest nontrivial case, namely, m = 4, q = 3.     

A Hamada type characterization of the classical geometric designs

The dimension of a combinatorial design ${{\mathcal D}}$ over a finite field F = GF(q) was defined in (Tonchev, Des Codes Cryptogr 17:121–128, 1999) as the minimum dimension of a linear code over F that contains the blocks of ${{\mathcal D}}$ as supports of nonzero codewords. There it was proved that, for any prime power q and any integer n ≥ 2, the dimension over F of a design ${{\mathcal D}}$ that has the same parameters as the complement of a classical point-hyperplane design PG _n-1(n, q) or AG _n-1(n, q) is greater than or equal to n + 1, with equality if and only if ${{\mathcal D}}$ is isomorphic to the complement of the classical design. It is the aim of the present paper to generalize this Hamada type characterization of the classical point-hyperplane designs in terms of associated codes over F = GF(q) to a characterization of all classical geometric designs PG _d (n, q), where 1 ≤ d ≤ n ? 1, in terms of associated codes defined over some extension field E?=?GF(q ^t ) of F. In the affine case, we conjecture an analogous result and reduce this to a purely geometric conjecture concerning the embedding of simple designs with the parameters of AG _d (n, q) into PG(n, q). We settle this problem in the affirmative and thus obtain a Hamada type characterization of AG _d (n, q) for d = 1 and for d > (n ? 2)/2.     

Necklaces,symmetries and self-reciprocal polynomials

The connection between a certain class of necklaces and self-reciprocal polynomials over finite fields is shown. For n?2, self-reciprocal polynomials of degree 2n arising from monic irreducible polynomials of degree n are shown to be either irreducible or the product or two irreducible factors which are necessarily reciprocal polynomials. Using DeBruijn's method we count the number of necklaces in this class and hence obtain a formula for the number of irreducible self-reciprocal polynomials showing that they exist for every even degree. Thus every extension of a finite field of even degree can be obtained by adjoining a root of an irreducible self-reciprocal polynomial.     

Enumeration of inequivalent irreducible Goppa codes

We consider irreducible Goppa codes over F_q of length qⁿ defined by polynomials of degree r, where q is a prime power and n,r are arbitrary positive integers. We obtain an upper bound on the number of such codes.     

Order of elements in the groups related to the general linear group

For a natural number n and a prime power q the general, special, projective general and projective special linear groups are denoted by GL_n(q), SL_n(q), PGL_n(q) and PSL_n(q), respectively. Using conjugacy classes of elements in GL_n(q) in terms of irreducible polynomials over the finite field GF(q) we demonstrate how the set of order elements in GL_n(q) can be obtained. This will help to find the order of elements in the groups SL_n(q), PGL_n(q) and PSL_n(q). We also show an upper bound for the order of elements in SL_n(q).