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.     

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 linear complexity of binary lattices,II

The linear complexity is an important and frequently used measure of unpredictably and pseudorandomness of binary sequences. In Part I of this paper, we extended this notion to two dimensions: we defined and studied the linear complexity of binary and bit lattices. In this paper, first we will estimate the linear complexity of a truly random bit (M,N)-lattice. Next we will extend the notion of k-error linear complexity to bit lattices. Finally, we will present another alternative definition of linear complexity of bit lattices.     

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.     

More constructions of pseudorandom sequences of k symbols

We present some new constructions of families of pseudorandom sequences of k symbols, which generalize several previous constructions for the binary case.     

Measures of pseudorandomness of finite binary lattices,II. (The symmetry measures)

In an earlier paper Gyarmati introduced and studied the symmetry measure of pseudorandomness of binary sequences. The goal of this paper is to extend this definition to two dimensions, i.e., to binary lattices. Three different definitions are proposed to do this extension. The connection between these definitions is analyzed. It is shown that these new symmetry measures are independent of the other measures of pseudorandomness of binary lattices. A binary lattice is constructed for which both the pseudorandom measures of order ℓ (for every fixed ℓ) and the symmetry measures are small. Finally, the symmetry measures are estimated for truly random binary lattices.     

Characterization of 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>-periodic binary sequences with fixed 2-error or 3-error linear complexity

The linear complexity of sequences is an important measure of the cryptographic strength of key streams used in stream ciphers. The instability of linear complexity caused by changing a few symbols of sequences can be measured using k-error linear complexity. In their SETA 2006 paper, Fu et al. (SETA, pp. 88–103, 2006) studied the linear complexity and the 1-error linear complexity of 2 ⁿ -periodic binary sequences to characterize such sequences with fixed 1-error linear complexity. In this paper we study the linear complexity and the k-error linear complexity of 2 ⁿ -periodic binary sequences in a more general setting using a combination of algebraic, combinatorial, and algorithmic methods. This approach allows us to characterize 2 ⁿ -periodic binary sequences with fixed 2- or 3-error linear complexity. Using this characterization we obtain the counting function for the number of 2 ⁿ -periodic binary sequences with fixed k-error linear complexity for k = 2 and 3.     

Class numbers of definite binary quadratic lattices over algebraic function fields

Let k be an algebraic function field of one variable X having a finite field GF(q) of constants with q elements, q odd. Confined to imaginary quadratic extensions $\text{K}\text{k}$, class number formulas are developed for both the maximal and nonmaximal binary quadratic lattices L on (K, N), where N denotes the norm from K to k. The class numbers of L grow either with the genus g(k) of k (assuming the fields under consideration have bounded degree) or with the relative genus $\text{g(}\text{K}\text{k}\text{)}$ (assuming the lattices under consideration have bounded scale). In contrast to analogous theorems concerning positive definite binary quadratic lattices over totally real number fields, k is not necessarily totally real.     

On new measures of pseudorandomness of binary lattices

Hubert, Mauduit and Sárközy introduced the pseudorandom measure of order ? of binary lattices. This measure studies the pseudorandomness only on box lattices of very special type. In certain applications one may need measures covering a more general situation. In this paper the line measure and the convex measure are introduced.     

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.     

Construction of pseudorandom binary sequences using additive characters over GF(2 k )

In a series of papers Mauduit and Sárközy (partly with coauthors) studied finite pseudorandom binary sequences and they constructed sequences with strong pseudorandom properties. In these constructions fields with prime order were used. In this paper a new construction is presented, which is based on finite fields of order 2 ^k .     

Coordinatization of finite join-distributive lattices

Join-distributive lattices are finite, meet-semidistributive, and semimodular lattices. They are the same as lattices with unique irreducible decompositions, introduced by R.P. Dilworth in 1940, and many alternative definitions and equivalent concepts have been discovered or rediscovered since then. Let L be a join-distributive lattice of length n, and let k denote the width of the set of join-irreducible elements of L. We prove that there exist k ? 1 permutations acting on {1, . . . , n} such that the elements of L are coordinatized by k-tuples over {0, . . . , n}, and the permutations determine which k-tuples are allowed. Since the concept of join-distributive lattices is equivalent to that of antimatroids and convex geometries, our result offers a coordinatization for these combinatorial structures.     

On constant composition codes

A constant composition code over a k-ary alphabet has the property that the numbers of occurrences of the k symbols within a codeword is the same for each codeword. These specialize to constant weight codes in the binary case, and permutation codes in the case that each symbol occurs exactly once. Constant composition codes arise in powerline communication and balanced scheduling, and are used in the construction of permutation codes. In this paper, direct and recursive methods are developed for the construction of constant composition codes.     

Positive definite binary hermitian forms with finitely many exceptions

Let E/F be a CM extension of number fields, and L be a positive definite binary hermitian lattice over the ring of integers of E. An element in F is called an exception of L if it is represented by every localization of L but not by L itself. We show that if E/F and a positive integer k are given, then there are only finitely many similarity classes of positive definite binary hermitian lattices with at most k exceptions. This generalizes the corresponding finiteness result by Earnest and Khosravani [A.G. Earnest, A. Khosravani, Representation of integers by positive definite binary hermitian lattices over imaginary quadratic fields, J. Number Theory 62 (1997) 368-374, Theorem 2.2] for the case F=Q. We also prove that for a fixed totally real field F of odd degree over Q, there are only finitely many CM extensions E/F for which there exists a positive definite regular normal binary hermitian lattice over the ring of integers of E.     

Periodic multisequences with large error linear complexity

Generalizing the theory of k-error linear complexity for single sequences over a finite field, Meidl et al. (J. Complexity 23(2), 169–192 (2007)) introduced three possibilities of defining error linear complexity measures for multisequences. A good keystream sequence must possess a large linear complexity and a large k-error linear complexity simultaneously for suitable values of k. In this direction several results on the existence, and lower bounds on the number, of single sequences with large k-error linear complexity were proved in Meidl and Niederreiter (Appl. Algebra Eng. Commun. Comput. 14(4), 273–286 (2003)), Niederreiter (IEEE Trans. Inform. Theory 49(2), 501–505 (2003)) and Niederreiter and Shparlinski (In: Paterson (ed.) 9th IMA International Conference on Cryptography and Coding (2003)). In this paper we discuss analogous results for the case of multisequences. We also present improved bounds on the error linear complexity and on the number of sequences satisfying such bounds for the case of single sequences.     

Asymptotic analysis on the normalized <Emphasis Type="Italic">k</Emphasis>-error linear complexity of binary sequences

Linear complexity and k-error linear complexity are the important measures for sequences in stream ciphers. This paper discusses the asymptotic behavior of the normalized k-error linear complexity \({L_{n,k}(\underline{s})/n}\) of random binary sequences \({\underline{s}}\) , which is based on one of Niederreiter’s open problems. For k = n θ, where 0 ≤ θ ≤ 1/2 is a fixed ratio, the lower and upper bounds on accumulation points of \({L_{n,k}(\underline{s})/n}\) are derived, which holds with probability 1. On the other hand, for any fixed k it is shown that \({\lim_{n\rightarrow\infty} L_{n,k}(\underline{s})/n = 1/2}\) holds with probability 1. The asymptotic bounds on the expected value of normalized k-error linear complexity of binary sequences are also presented.     

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.     

A note on certain de Bruijn sequences with forbidden subsequences

We consider words over a finite alphabet with certain uniqueness properties (a subsequence of length k does not occur more than once) and distance properties (at least j other symbols separate the occurrence of the same symbol). The maximal length of these words is realised by linear de Bruijn sequences with certain forbidden subsequences. We prove the existence of these maximal sequences.     

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.     

Distribution of the full rank in residue classes for odd moduli

The distribution of values of the full ranks of marked Durfee symbols is examined in prime and nonprime arithmetic progressions. The relative populations of different residues for the same modulus are determined: the primary result is that k-marked Durfee symbols of n equally populate the residue classes a and bmod2k+1 if gcd(a,2k+1)=gcd(b,2k+1). These are used to construct a few congruences. The general procedure is illustrated with a particular theorem on 4-marked symbols for multiples of 3.