Sparse polynomials, redundant bases, gauss periods, and efficient exponentiation of primitive elements for small characteristic finite fields

Gauss periods give an exponentiation algorithm that is fast for many finite fields but slow for many other fields. The current paper presents a different method for construction of elements that yield a fast exponentiation algorithm for finite fields where the Gauss period method is slow or does not work. The basic idea is to use elements of low multiplicative order and search for primitive elements that are binomial or trinomial of these elements. Computational experiments indicate that such primitive elements exist, and it is shown that they can be exponentiated fast.     

Abelian Groups,Gauss Periods,and Normal Bases

A result on finite abelian groups is first proved and then used to solve problems in finite fields. Particularly, all finite fields that have normal bases generated by general Gauss periods are characterized and it is shown how to find normal bases of low complexity.     

Gauss periods as constructions of low complexity normal bases

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

Strongly regular Cayley graphs and rationality of relative Gauss sums

In this note, we give a construction of strongly regular Cayley graphs. The presented construction is based on choosing cyclotomic classes in finite fields, and our results generalize ten of the eleven sporadic examples of cyclotomic strongly regular graphs given by Schmidt and White [B. Schmidt, C. White, All two-weight irreducible cyclic codes, Finite Fields Appl. 8 (2002), 321–367] into infinite families. These infinite families of strongly regular graphs have new parameters. The main tools that we employed are relative Gauss sums instead of explicit evaluations of Gauss sums.     

Strongly regular Cayley graphs,skew Hadamard difference sets,and rationality of relative Gauss sums

In this paper, we give constructions of strongly regular Cayley graphs and skew Hadamard difference sets. Both constructions are based on choosing cyclotomic classes in finite fields. Our results generalize ten of the eleven sporadic examples of cyclotomic strongly regular graphs given by Schmidt and White (2002) [23] and several subfield examples into infinite families. These infinite families of strongly regular graphs have new parameters. The main tools that we employed are relative Gauss sums instead of explicit evaluations of Gauss sums.     

Elements of high order in finite fields of the form Fq[x]/Φr(x)

We obtain explicit lower bounds on multiplicative orders of finite field elements that have more general form than Gauss periods of a special type. This bound improves in a partial case of Gauss period the previous bound of Ahmadi, Shparlinski and Voloch (2010) [2].     

二元叠加码M_q(n,k,d)码的平均汉明距离和均方差

根据二元叠加码(Binary Superimposed Code)M_q(n,k,d)的定义及有限域F_q上n维向量空间的k维子空间的维数性质定义了一个高斯组合函数,利用这个组合函数研究了M_q(n,k,d)码的平均汉明(Hamming)距离和它的均方差问题,给出了计算公式.     

Some results on strongly regular graphs from unions of cyclotomic classes

In this paper, we construct some families of strongly regular graphs on finite fields by using unions of cyclotomic classes and index 2 Gauss sums. New infinite families of strongly regular graphs are found.     

Gauss sums over some matrix groups

In this note, we give explicit expressions of Gauss sums for general (resp. special) linear groups over finite fields, which involve classical Gauss sums (resp. Kloosterman sums). The key ingredient is averaging such sums over Borel subgroups, i.e., the groups of upper triangular matrices. As applications, we count the number of invertible matrices of zero-trace over finite fields and we also improve two bounds of Ferguson, Hoffman, Luca, Ostafe and Shparlinski in [R. Ferguson, C. Hoffman, F. Luca, A. Ostafe, I.E. Shparlinski, Some additive combinatorics problems in matrix rings, Rev. Mat. Complut. 23 (2010) 501–513].     

On some questions related to the Gauss conjecture for function fields

We show that, for any finite field Fq, there exist infinitely many real quadratic function fields over Fq such that the numerator of their zeta function is a separable polynomial. As pointed out by Anglès, this is a necessary condition for the existence, for any finite field Fq, of infinitely many real function fields over Fq with ideal class number one (the so-called Gauss conjecture for function fields). We also show conditionally the existence of infinitely many real quadratic function fields over Fq such that the numerator of their zeta function is an irreducible polynomial.     

Three-valued Gauss periods,circulant weighing matrices and association schemes

Gauss periods taking exactly two values are closely related to two-weight irreducible cyclic codes and strongly regular Cayley graphs. They have been extensively studied in the work of Schmidt and White and others. In this paper, we consider the question of when Gauss periods take exactly three rational values. We obtain numerical necessary conditions for Gauss periods to take exactly three rational values. We show that in certain cases, the necessary conditions obtained are also sufficient. We give numerous examples where the Gauss periods take exactly three values. Furthermore, we discuss connections between three-valued Gauss periods and combinatorial structures such as circulant weighing matrices and three-class association schemes.     

On the convergence of basic iterative methods for convection–diffusion equations

In this paper we analyze convergence of basic iterative Jacobi and Gauss–Seidel type methods for solving linear systems which result from finite element or finite volume discretization of convection–diffusion equations on unstructured meshes. In general the resulting stiffness matrices are neither M‐matrices nor satisfy a diagonal dominance criterion. We introduce two newmatrix classes and analyse the convergence of the Jacobi and Gauss–Seidel methods for matrices from these classes. A new convergence result for the Jacobi method is proved and negative results for the Gauss–Seidel method are obtained. For a few well‐known discretization methods it is shown that the resulting stiffness matrices fall into the new matrix classes. Copyright © 1999 John Wiley & Sons, Ltd.     

Fourier transform over finite field and identities between Gauss sums

This paper is a sequel to [7]. Here we study identities for the Fourier transform of "elementary functions" over finite fields containing "exponentials" of rational monomial functions. It turns out that these identities are governed by monomial identities between Gauss sums. We show that similar to the case of complex numbers such identities correspond to linear relations between certain divisors on the space of multiplicative characters.     

The weight distributions of a class of cyclic codes

Recently, the weight distributions of the duals of the cyclic codes with two zeros have been obtained for several cases in Ma et al. (2011) [14], Ding et al. (2011) [5], Wang et al. (2011) [20]. In this paper we provide a slightly different approach toward the general problem and use it to solve one more special case. We make extensive use of standard tools in number theory such as characters of finite fields, the Gauss sums and the Jacobi sums to transform the problem of finding the weight distribution into a problem of evaluating certain character sums over finite fields, which on the special case is related with counting the number of points on some elliptic curves over finite fields. Other cases are also possible by this method.     

Preconditioning cubic spline collocation discretizations of elliptic equations

Summary. This work considers the uniformly elliptic operator defined by in (the unit square) with boundary conditions: on and on and its discretization based on Hermite cubic spline spaces and collocation at the Gauss points. Using an interpolatory basis with support on the Gauss points one obtains the matrix . We discuss the condition numbers and the distribution of -singular values of the preconditioned matrices where is the stiffness matrix associated with the finite element discretization of the positive definite uniformly elliptic operator given by in with boundary conditions: on on . The finite element space is either the space of continuous functions which are bilinear on the rectangles determined by Gauss points or the space of continuous functions which are linear on the triangles of the triangulation of using the Gauss points. When we obtain results on the eigenvalues of . In the general case we obtain bounds and clustering results on the -singular values of . These results are related to the results of Manteuffel and Parter [MP], Parter and Wong [PW], and Wong [W] for finite element discretizations as well as the results of Parter and Rothman [PR] for discretizations based on Legendre Spectral Collocation. Received January 1, 1994 / Revised version received February 7, 1995     

广义对角多项式指数和的估计

利用高斯和与次数矩阵Smith标准形的不变因子,给出了有限域上广义对角多项式指数和的估计,从而改进了Deligne-Weil型估计这类多项式指数和的结果.     

Second order linear sequence subgroups in finite fields—II

In previous papers [O.J. Brison, J.E. Nogueira, Linear recurring sequence subgroups in finite fields, Finite Fields Appl. 9 (2003) 413–422; O.J. Brison, J.E. Nogueira, Second order linear sequence subgroups in finite fields, Finite Fields Appl. 14 (2008) 277–290] the authors investigated when, and how, a multiplicative subgroup of a finite field can be written, without repetition, as a cyclically-closed second order recurring sequence. Here, the earlier results are extended for sequences with certain restricted periods.     

Gauss sums forF q [T]

The purpose of this paper is to define Gauss sums taking values in function fields of one variable over a finite field and to prove analogues of various classical and recent results. These results include Stickelberger's theorem, the Hasse-Davenport theorem, Weil's theorem on Jacobi sums as Hecke characters and the Gross-Koblitz theorem. For comparison, the reader may consult [G-K] and references given there.In this paper we deal only with the simplest case, where the base ringA is the polynomial ringF _q [T] and where we use the Carlitz module; i.e., the simplest rank one Drinfeld module. (See section I). The general case, which has a quite different flavour, will be presented elsewhere. These results formed a part of the author's thesis, Gamma functions and Gauss sums for function fields and periods of Drinfeld modules (Harvard 1987). But the new presentation here is due to a suggestion by Professor Tate. It is my pleasure to thank him.Supported in part by NSF grant DMS 8610730C2     

Constructions of strongly regular Cayley graphs using index four Gauss sums

We give a construction of strongly regular Cayley graphs on finite fields $\mathbb{F}_{q}$ by using union of cyclotomic classes and index 4 Gauss sums. In particular, we obtain two infinite families of strongly regular graphs with new parameters.     

Gauss sums and multinomial coefficients

Consider a Gauss sum for a finite field of characteristic p, where p is an odd prime. When such a sum (or a product of such sums) is a p-adic integer we show how it can be realized as a p-adic limit of a sequence of multinomial coefficients. As an application we generalize some congruences of Hahn and Lee to exhibit p-adic limit formulae, in terms of multinomial coefficients, for certain algebraic integers in imaginary quadratic fields related to the splitting of rational primes. We also give an example illustrating how such congruences arise from a p-integral formal group law attached to the p-adic unit part of a product of Gauss sums.