Construction of pseudorandom binary sequences using additive characters over GF(2<Superscript><Emphasis Type="Italic">k</Emphasis></Superscript>) II

In a series of papers Mauduit and Sárközy introduced measures of pseudorandomness and they constructed large families of sequences with strong pseudorandom properties. In later papers the structure of families of binary sequences was also studied. In these constructions fields with prime order were used. Throughout this paper the structure of a family of binary sequences based on GF(2 ^k ) will be studied.     

Extension of the notion of collision and avalanche effect to sequences of k symbols

In recent papers [14], [15] I studied collision and avalanche effect in families of finite pseudorandom binary sequences. Motivated by applications, Mauduit and Sárk?zy in [13] generalized and extended this theory from the binary case to k-ary sequences, i.e., to k symbols. They constructed a large family of k-ary sequences with strong pseudorandom properties. In this paper our goal is to extend the study of the pseudorandom properties mentioned above to k-ary sequences. The aim of this paper is twofold. First we will extend the definitions of collision and avalanche effect to k-ary sequences, and then we will study these related properties in a large family of pseudorandom k-ary sequences with ??small?? pseudorandom measures.     

On finite pseudorandom lattices of k symbols

In earlier papers Mauduit and Sárközy have introduced and studied the measures of pseudorandomness for finite binary sequences and sequences of k symbols. Later they (with further coauthors) extended the notation of binary sequences to binary lattices. In this paper measures of pseudorandom lattices of k symbols are introduced and studied for “truly random” lattices.     

On finite pseudorandom sequences of k symbols

In earlier papers C. Mauduit and A. Sárközy have introduced and studied the measures of pseudorandomness for finite binary sequences. In [8] they extend this theory to sequences of k symbols: they give the definitions and also construct a “good” pseudorandom sequence of k symbols. In this paper these measures are studied for a “truely random” sequence.     

A complexity measure for families of binary sequences

In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography) it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated. This revised version was published online in August 2006 with corrections to the Cover Date.     

Construction of large families of pseudorandom binary sequences

Oon constructed large families of finite binary sequences with strong pseudorandom properties by using Dirichlet characters of large order. In this paper Oon’s construction is generalized and extended. We prove that in our construction the well-distribution and correlation measures are as “small” as in the case of the Legendre symbol.      

Exponential sums of nonlinear congruential pseudorandom number generators with Rédei functions

The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. We give new bounds of exponential sums with sequences of iterations of Rédei functions over prime finite fields, which are much stronger than bounds known for general nonlinear congruential pseudorandom number generators.     

Lower bounds for the discrepancy of triples of inversive congruential pseudorandom numbers with power of two modulus

This paper deals with the inversive congruential method with power of two modulusm for generating uniform pseudorandom numbers. Statistical independence properties of the generated sequences are studied based on the distribution of triples of successive pseudorandom numbers. It is shown that there exist parameters in the inversive congruential method such that the discrepancy of the corresponding point sets in the unit cube is of an order of magnitude at leastm ^–1/3. The method of proof relies on a detailed analysis of certain rational exponential sums.     

Modified constructions of binary sequences using multiplicative inverse

Two new families of finite binary sequences are constructed using multiplicative inverse. The sequences are shown to have strong pseudorandom properties by using some estimates of certain exponential sums over finite fields. The constructions can be implemented fast since multiplicative inverse over finite fields can be computed in polynomial time.     

On the pseudorandomness of quaternary sequences derived from sequences over $$\mathbb F_4$$

In analogy to the corresponding measures of pseudorandomness for quaternary sequences introduced by Mauduit and Sárközy (for m-ary sequences) we introduce the well-distribution measure and correlation measure of order k for sequences over \(\mathbb F_4\). Using any fixed bijection from \(\mathbb F_4\) to the set of complex fourth roots of unity, we analyze the relation of these pseudorandomness measures for sequences over \(\mathbb F_4\) and for the corresponding quaternary sequences. More precisely, we show that they differ only by a multiplicative constant (depending only on k). We also apply the results for deriving new quaternary pseudorandom sequences from pseudorandom sequences over \(\mathbb F_4\) and vice versa.     

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.

     

Measures of pseudorandomness for binary sequences constructed using finite fields

We extend the results of Goubin, Mauduit and Sárközy on the well-distribution measure and the correlation measure of order k of the sequence of Legendre sequences with polynomial argument in several ways. We analyze sequences of quadratic characters of finite fields of prime power order and consider in each case two, in general, different definitions of well-distribution measure and correlation measure of order k, respectively.     

Polynomial normal forms with exponentially small remainder for analytic vector fields

A key tool in the study of the dynamics of vector fields near an equilibrium point is the theory of normal forms, invented by Poincaré, which gives simple forms to which a vector field can be reduced close to the equilibrium. In the class of formal vector valued vector fields the problem can be easily solved, whereas in the class of analytic vector fields divergence of the power series giving the normalizing transformation generally occurs. Nevertheless the study of the dynamics in a neighborhood of the origin can very often be carried out via a normalization up to finite order. This paper is devoted to the problem of optimal truncation of normal forms for analytic vector fields in R^m. More precisely we prove that for any vector field in R^m admitting the origin as a fixed point with a semi-simple linearization, the order of the normal form can be optimized so that the remainder is exponentially small. We also give several examples of non-semi-simple linearization for which this result is still true.     

Corps euclidiens,unités exceptionnelles et courbes elliptiques

Lenstra [Invent. Math.36 (1977), 237–254] has proved that a number field possessing sequences of integers whose differences are units, having a big enough length with respect to the discriminant of the field, is Euclidean. In this paper, we use this result to construct some new Euclidean fields; suitable sequences are obtained by using points of finite order on some elliptic curves.     

Correlation of the two-prime Sidel��nikov sequence

Motivated by the concepts of Sidel??nikov sequences and two-prime generator (or Jacobi sequences) we introduce and analyze some new binary sequences called two-prime Sidel??nikov sequences. In the cases of twin primes and cousin primes equivalent 3 modulo 4 we show that these sequences are balanced. In the general case, besides balancedness we also study the autocorrelation, the correlation measure of order k and the linear complexity profile of these sequences showing that they have many nice pseudorandom features.     

Correlation measure,linear complexity and maximum order complexity for families of binary sequences

The correlation measure of order k is an important measure of pseudorandomness for binary sequences. This measure tries to look for dependence between several shifted versions of a sequence. We study the relation between the correlation measure of order k and two other pseudorandom measures: the Nth linear complexity and the Nth maximum order complexity. We simplify and improve several state-of-the-art lower bounds for these two measures using the Hamming bound as well as weaker bounds derived from it.     

Commutative presemifields and semifields

Strong conditions are derived for when two commutative presemifields are isotopic. It is then shown that any commutative presemifield of odd order can be described by a planar Dembowski-Ostrom polynomial and conversely, any planar Dembowski-Ostrom polynomial describes a commutative presemifield of odd order. These results allow a classification of all planar functions which describe presemifields isotopic to a finite field and of all planar functions which describe presemifields isotopic to Albert's commutative twisted fields. A classification of all planar Dembowski-Ostrom polynomials over any finite field of order p³, p an odd prime, is therefore obtained. The general theory developed in the article is then used to show the class of planar polynomials X¹⁰+aX⁶−a²X² with a≠0 describes precisely two new commutative presemifields of order e³ for each odd e?5.     

Rational places in extensions and sequences of function fields of Kummer type

In this paper we prove results on the number of rational places in extensions of Kummer type over finite fields and give sufficient conditions for non-trivial lower bounds on the number of rational places at each step of sequences of function fields over a finite field, that we call (a, b)-sequences. In the case of a prime field, we apply these results to the study of rational places in certain sequences of function fields of Kummer type.     

Construction of large families of pseudorandom binary sequences

In a series of papers Mauduit and Sárközy (partly with coauthors) studied finite pseudorandom binary sequences. They showed that the Legendre symbol forms a “good” pseudorandom sequence, and they also tested other sequences for pseudorandomness, however, no large family of “good” pseudorandom sequences has been found yet.In this paper, a large family of this type is constructed by extending the earlier Legendre symbol construction.     

Exponential sums with Dickson polynomials

We give new bounds of exponential sums with sequences of iterations of Dickson polynomials over prime finite fields. This result is motivated by possible applications to polynomial generators of pseudorandom numbers.