The discrete logarithm problem from a local duality perspective

The discrete logarithm problem is analyzed from the perspective of Tate local duality. Local duality in the multiplicative case and the case of Jacobians of curves over p-adic local fields are considered. When the local field contains the necessary roots of unity, the case of curves over local fields is polynomial time reducible to the multiplicative case, and the multiplicative case is polynomial time equivalent to computing discrete logarithm in finite fields. When the local field does not contains the necessary roots of unity, similar results can be obtained at the cost of going to an extension that contains these roots of unity. There was evidence in the analysis that suggests that the minimal extension where the local duality can be rationally and algorithmically defined must contain the roots of unity. Therefore, the discrete logarithm problem appears to be well protected against an attack using local duality. These results are also of independent interest for algorithmic study of arithmetic duality as they explicitly relate local duality in the case of curves over local fields to the multiplicative case and Tate-Lichtenbaum pairing (over finite fields).     

Construction of pseudorandom binary sequences by using the multiplicative inverse

Summary By using the multiplicative inverse modulo p, a large family of finite binary sequences is constructed with strong pseudorandom properties. The crucial tool in the proofs is an (additive) character sum estimate of Eichenauer--Hermann and Niederreiter.     

Construction of pseudorandom binary lattices by using the multiplicative inverse

In an earlier work Hubert and the authors of this paper introduced and studied the notion of pseudorandomness of binary lattices. Later in another paper the authors gave a construction for a large family of “good” binary lattices by using the quadratic characters of finite fields. Here, a further large family of “good” binary lattices is constructed by using finite fields and the notion of multiplicative inverse.     

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.     

On evaluating multivariate polynomials over finite fields

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

Gauss periods: orders and cryptographical applications

Experimental results on the multiplicative orders of Gauss periods in finite fields are presented. These results indicate that Gauss periods have high order and are often primitive (self-dual) normal elements in finite fields. It is shown that Gauss periods can be exponentiated in quadratic time. An application is an efficient pseudorandom bit generator.

     

On the Multiplicative Complexity of the Inversion and Division of Hamiltonian Quaternions

The multiplicative complexity of a finite set of rational functions is the number of essential multiplications and divisions that are necessary and sufficient to compute these rational functions. We prove that the multiplicative complexity of inversion in the division algebra \H of Hamiltonian quaternions over the reals, that is, the multiplicative complexity of the coordinates of the inverse of a generic element from \H , is exactly eight. Furthermore, we show that the multiplicative complexity of the left and right division of Hamiltonian quaternions is at least eleven. July 17, 2001. Final version received: October 8, 2001.     

Generalizing pairs of complementary sequences and a construction of combinatorial structures

Pairs of complementary sequences such as Golay pairs have zero sum autocorrelation at all non-trivial phases. Several generalizations are known where conditions on either the autocorrelation function, or the entries of the sequences are altered. We aim to unify most of these ideas by introducing autocorrelation functions that apply to any sequences with entries in a set equipped with a ring-like structure which is closed under multiplication and contains multiplicative inverses. Depending on the elements of the chosen set, the resulting complementary pairs may be used to construct a variety of combinatorial structures such as Hadamard matrices, complex generalized weighing matrices, and signed group weighing matrices. We may also construct quasi-cyclic and quasi-constacyclic linear codes which over finite fields of order less than 5 are also Hermitian self-orthogonal. As the literature on binary and ternary Golay sequences is already quite deep, one intention of this paper is to survey and assimilate work on more general pairs of complementary sequences and related constructions of combinatorial objects, and to combine the ideas into a single theoretical framework.     

Exact values of the sums of multiplicative characters of polynomials over finite fields

We give explicit constructions of polynomials of special form over finite fields the sum of whose multiplicative characters is exactly known.     

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.     

On modeling with multiplicative differential equations

This work is aimed to show that various problems from different fields can be modeled more efficiently using multiplicative calculus, in place of Newtonian calculus. Since multiplicative calculus is still in its infancy, some effort is put to explain its basic principles such as exponential arithmetic, multiplicative calculus, and multiplicative differential equations. Examples from finance, actuarial science, economics, and social sciences are presented with solutions using multiplicative calculus concepts. Based on the encouraging results obtained it is recommended that further research into this field be vested to exploit the applicability of multiplicative calculus in different fields as well as the development of multiplicative calculus concepts.     

Integral points for groups of multiplicative type

We construct a finite subgroup of Brauer–Manin obstruction for detecting the existence of integral points on integral models of homogeneous spaces of linear algebraic groups of multiplicative type. As an application, the strong approximation theorem for linear algebraic groups of multiplicative type is established. Moreover, the sum of two integral squares over some quadratic fields is discussed.     

Inverse eigenvalue problems

The classical inverse additive and multiplicative inverse eigenvalue problems for matrices are studied. Using general results on the solvability of polynomial systems it is shown that in the complex case these problems are always solvable by a finite number of solutions. In case of real symmetric matrices the inverse problems are reformulated to have a real solution. An algorithm is given to obtain this solution.     

Construction of pseudorandom binary lattices by using the multiplicative inverse

In an earlier work Hubert and the authors of this paper introduced and studied the notion of pseudorandomness of binary lattices. Later in another paper the authors gave a construction for a large family of “good” binary lattices by using the quadratic characters of finite fields. Here, a further large family of “good” binary lattices is constructed by using finite fields and the notion of multiplicative inverse. Authors’ addresses: Christian Mauduit, Institut de Mathématiques de Luminy, CNRS, UMR 6206, 163 avenue de Luminy, Case 907, F-13288 Marseille Cedex 9, France; András Sárk?zy, Department of Algebra and Number Theory, E?tv?s Loránd University, Pázmány Péter sétány 1/C, H-1117 Budapest, Hungary     

On Weil's proof of the bound for Kloosterman sums

While most proofs of the Weil bound on one-variable Kloosterman sums over finite fields are carried out in all characteristics, the original proof of this bound, by Weil, assumes the characteristic is odd. We show how to make Weil's argument work in even characteristic, for both ordinary Kloosterman sums and sums twisted by a multiplicative character.     

Some multiplicative equations in finite fields

In this paper we consider estimating the number of solutions to multiplicative equations in finite fields when the variables run through certain sets with high additive structure. In particular, we consider estimating the multiplicative energy of generalized arithmetic progressions in prime fields and of boxes in arbitrary finite fields. We obtain sharp bounds in more general scenarios than previously known. Our arguments extend some ideas of Konyagin and Bourgain and Chang into new settings.     

Construction of long MDS self-dual codes from short codes

In this paper, we propose a mechanism on how to construct long MDS self-dual codes from short ones. These codes are special types of generalized Reed-Solomon (GRS) codes or extended generalized Reed-Solomon codes. The main tool is utilizing additive structure or multiplicative structure on finite fields. By applying this method, more MDS self-dual codes can be constructed.     

Cubic structures and ideal class groups

We establish a generalization of Breen's theory of cubic structures on line bundles over group schemes. We study such “n-cubic structures” inductively using multiextensions. As a result we obtain information on the set of isomorphism classes of line bundles with n-cubic structures over finite multiplicative group schemes over Spec(Z) by relating this set to certain corresponding eigenspaces of ideal class groups of cyclotomic fields.     

Triviality of universal norms on formal groups over a local field

A result of the local theory of class fields on the triviality of universal norms on a multiplicative group is generalized to the case of an arbitrary commutative multiparametric formal group defined over the ring of integers of a complete discretely normed field with a finite residue field.     

Construction of pseudorandom binary lattices based on multiplicative characters

In this paper a large family of pseudorandom binary lattices is constructed by using the multiplicative characters of finite fields. This construction generalizes several one-dimensional constructions to arbitrary dimensions.