Search

This paper is concerned with constructions and orthogonality of generalized Sudoku arrays of various forms. We characterize these arrays based on their constraints; for example Sudoku squares are characterized by having strip and sub-square constraints. First, we generalize Sudoku squares to be multi-dimensional arrays with strip and sub-cube constraints and construct mutually orthogonal sets of these arrays using linear polynomials. We add additional constraints motivated by elementary intervals for low discrepancy sequences and again give a construction of these arrays using linear polynomials in detail for 3 dimensional and a general construction method for arbitrary dimension. Then we give a different construction of these hypercubes due to MDS codes. We also analyze the orthogonality of all of the Sudoku-like hypercubes we consider in this paper.

Optimal normal bases are special cases of the so-called Gauss periods (Disquisitiones Arithmeticae, Articles 343---366); in particular, optimal normal bases are Gauss periods of type (n, 1) for any characteristic and of type (n, 2) for characteristic 2. We present the multiplication tables and complexities of Gauss periods of type (n, t) for all n and t = 3, 4, 5 over any finite field and give a slightly weaker result for Gauss periods of type (n, 6). In addition, we give some general results on the so-called cyclotomic numbers, which are intimately related to the structure of Gauss periods. We also present the general form of a normal basis obtained by the trace of any normal basis in a finite extension field. Then, as an application of the trace construction, we give upper bounds on the complexity of the trace of a Gauss period of type (n, 3).

Swan (Pac. J. Math. 12:1099---1106, 1962) gives conditions under which the trinomial x n + x k + 1 over $${\mathbb{F}_{2}}$$ is reducible. Vishne (Finite Fields Appl. 3:370---377, 1997) extends this result to trinomials over extensions of $${\mathbb{F}_{2}}$$ . In this work we determine the parity of the number of irreducible factors of all binomials and some trinomials over the finite field $${\mathbb{F}_{q}}$$ , where q is a power of an odd prime.

Let $${\mathbb{F}}_{q}$$ be a finite field and consider an extension $${\mathbb{F}}_{q^{n}}$$ where an optimal normal element exists. Using the trace of an optimal normal element in $${\mathbb{F}}_{q^{n}}$$ , we provide low complexity normal elements in $${\mathbb{F}}_{q^{m}}$$ , with m = n/k. We give theorems for Type I and Type II optimal normal elements. When Type I normal elements are used with m = n/2, m odd and q even, our construction gives Type II optimal normal elements in $${\mathbb{F}}_{q^{m}}$$ ; otherwise we give low complexity normal elements. Since optimal normal elements do not exist for every extension degree m of every finite field $${\mathbb{F}}_{q}$$ , our results could have a practical impact in expanding the available extension degrees for fast arithmetic using normal bases.