The expectation and variance of the joint linear complexity of random periodic multisequences

The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, in the study of vectorized stream cipher systems, the joint linear complexity of multisequences has been investigated. By using the generalized discrete Fourier transform for multisequences, Meidl and Niederreiter determined the expectation of the joint linear complexity of random N-periodic multisequences explicitly. In this paper, we study the expectation and variance of the joint linear complexity of random periodic multisequences. Several new lower bounds on the expectation of the joint linear complexity of random periodic multisequences are given. These new lower bounds improve on the previously known lower bounds on the expectation of the joint linear complexity of random periodic multisequences. By further developing the method of Meidl and Niederreiter, we derive a general formula and a general upper bound for the variance of the joint linear complexity of random N-periodic multisequences. These results generalize the formula and upper bound of Dai and Yang for the variance of the linear complexity of random periodic sequences. Moreover, we determine the variance of the joint linear complexity of random periodic multisequences with certain periods.     

Error linear complexity measures for multisequences

Complexity measures for sequences over finite fields, such as the linear complexity and the k-error linear complexity, play an important role in cryptology. Recent developments in stream ciphers point towards an interest in word-based stream ciphers, which require the study of the complexity of multisequences. We introduce various options for error linear complexity measures for multisequences. For finite multisequences as well as for periodic multisequences with prime period, we present formulas for the number of multisequences with given error linear complexity for several cases, and we present lower bounds for the expected error linear complexity.     

Linear complexity profile of m-ary pseudorandom sequences with small correlation measure

We estimate the linear complexity profile of m-ary sequences in terms of their correlation measure, which was introduced by Mauduit and Sárközy. For prime m this is a direct extension of a result of Brandstätter and the second author. For composite m, we define a new correlation measure for m-ary sequences, relate it to the linear complexity profile and estimate it in terms of the original correlation measure. We apply our results to sequences of discrete logarithms modulo m and to quaternary sequences derived from two Legendre sequences.     

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.     

基于代数曲线上具有高广义联合线性复杂度的多重序列

多重序列的联合线性复杂度是衡量基于字的流密码体系安全的一个重要指标. 由元素取自F_q上的m 重序列和元素取自F_q^m 上的单个序列之间的一一对应, Meidl 和Özbudak 定义多重序列的广义联合线性复杂度为对应的单个序列的线性复杂度. 在本文中, 我们利用代数曲线的常数域扩张, 研究两类多重序列的广义联合线性复杂度. 更进一步, 我们指出这两类多重序列同时具有高联合线性复杂度和高广义联合线性复杂度.     

Multisequences with large linear and k-error linear complexity from a tower of Artin–Schreier extensions of function fields

In this paper, we construct multisequences with both large (joint) linear complexity and k-error (joint) linear complexity from a tower of Artin–Schreier extensions of function fields. Moreover, these sequences can be explicitly constructed.     

Block companion Singer cycles, primitive recursive vector sequences, and coprime polynomial pairs over finite fields

We discuss a conjecture concerning the enumeration of nonsingular matrices over a finite field that are block companion and whose order is the maximum possible in the corresponding general linear group. A special case is proved using some recent results on the probability that a pair of polynomials with coefficients in a finite field is coprime. Connection with an older problem of Niederreiter about the number of splitting subspaces of a given dimension are outlined and an asymptotic version of the conjectural formula is established. Some applications to the enumeration of nonsingular Toeplitz matrices of a given size over a finite field are also discussed.     

On the joint linear complexity profile of explicit inversive multisequences

We prove lower bounds on the joint linear complexity profile of multisequences obtained by explicit inversive methods and show that for some suitable choices of parameters these joint linear complexity profiles are close to be perfect.     

Around Pelikán’s conjecture on very odd sequences

Very odd sequences were introduced in 1973 by Pelikán who conjectured that there were none of length 5. This conjecture was disproved first by MacWilliams and Odlyzko [17] in 1977 and then by two different sets of authors in 1992 [1], 1995 [9]. We give connections with duadic codes, cyclic difference sets, levels (Stufen) of cyclotomic fields, and derive some new asymptotic results on the length of very odd sequences and the number of such sequences of a given length.     

Elliptic curve analogue of Legendre sequences

The Legendre symbol is applied to the rational points over an elliptic curve to output a family of binary sequences with strong pseudorandom properties. That is, both the well-distribution measure and the correlation measure of order k, which are evaluated by using estimation of certain character sums along elliptic curves, of the resulting binary sequences are “small”. A lower bound on the linear complexity profile of these sequences is also presented. Our results indicate that the behavior of such sequences is very similar to that of the Legendre sequences. Research partially supported by the Science and Technology Foundation of Putian City (No. 2005S04), the Open Funds of Key Lab of Fujian Province University Network Security and Cryptology (No. 07B005) and the Foundation of the Education Department of Fujian Province (No. JA07164). Author’s addresses: Department of Mathematics, Putian University, Putian, Fujian 351100, China; and Key Lab of Network Security and Cryptology, Fujian Normal University, Fuzhou, Fujian 350007, China     

Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources

The semi-random source, defined by Sántha and Vazirani, is a general mathematical mode for imperfect and correlated sources of randomness (physical sources such as noise dicdes). In this paper an algorithm is presented which efficiently generates “high quality” random sequences (quasirandom bit-sequences) from two independent semi-random sources. The general problem of extracting “high quality” bits is shown to be related to communication complexity theory, leading to a definition of strong communication complexity of a boolean function. A hierarchy theorem for strong communication complexity classes is proved; this allows the previous algorithm to be generalized to one that can generate quasi-random sequences from two communicating semi-random sources This research was supported in part by an IBM Doctoral Felloswhip and by NSF Grant MCS 82-04506.     

Successive minima profile,lattice profile,and joint linear complexity profile of pseudorandom multisequences

In this paper we use the successive minima profile to measure structural properties of pseudorandom multisequences. We show that both the lattice profile and the joint linear complexity profile of a multisequence can be expressed in terms of the successive minima profile.     

Random quantum channels II: Entanglement of random subspaces, Rényi entropy estimates and additivity problems

In this paper we obtain new bounds for the minimum output entropies of random quantum channels. These bounds rely on random matrix techniques arising from free probability theory. We then revisit the counterexamples developed by Hayden and Winter to get violations of the additivity equalities for minimum output Rényi entropies. We show that random channels obtained by randomly coupling the input to a qubit violate the additivity of the p-Rényi entropy, for all p>1. For some sequences of random quantum channels, we compute almost surely the limit of their Schatten S₁→Sp norms.     

Invariants of modular groups

For a faithful linear representation of a finite group G over a field of characteristic p, we study the ring of invariants. We especially study the polynomial and Cohen–Macaulay properties of the invariant ring. We first show that certain quotient rings of the invariant ring are polynomial rings by which we prove that the Hilbert ideal conjecture is true for a class of groups. In particular, we prove that the conjecture is true for vector invariant rings of Abelian reflection p-groups. Then we study the relationships between the invariant ring of G and that of a subgroup of G. Finally, we study the invariant rings of affine groups and show that, over a finite field, if an affine group contains all translations then the invariant ring is isomorphic to the invariant ring of a linear group.     

On the linear complexity of Hall’s sextic residue sequences over $${ GF}(q)$$

In this paper, we derive the linear complexity of Hall’s sextic residue sequences over the finite field of odd prime order. The order of the field is not equal to a period of the sequence. Our results show that Hall’s sextic residue sequences have high linear complexity over the finite field of odd order. Also we estimate the linear complexity of series of generalized sextic cyclotomic sequences. The linear complexity of these sequences is larger than half of the period.     

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.     

Data compression and histograms

Summary In this paper, the relationship between code length and the selection of the number of bins for a histogram density is considered for a sequence of iid observations on [0,1]. First, we use a shortest code length criterion to select the number of bins for a histogram. A uniform almost sure asymptotic expansion for the code length is given and it is used to prove the asymptotic optimality of the selection rule. In addition, the selection rule is consistent if the true density is uniform [0,1]. Secondly, we deal with the problem: what is the best achievable average code length with underlying density functionf? Minimax lower bounds are derived for the average code length over certain smooth classes of underlying densitiesf. For the smooth class with bounded first derivatives, the rate in the lower bound is shown to be achieved by a code based on a sequence of histograms whose number of bins is changed predictively. Moreover, this best code can be modified to ensure that the almost sure version of the code length has asymptotically the same behavior as its expected value, i.e., the average code length.Research supported in part by NSF grant DMS-8701426Research supported in part by NSF grant DMS-8802378     

An Ansatz for the asymptotics of hypergeometric multisums

Sequences that are defined by multisums of hypergeometric terms with compact support occur frequently in enumeration problems of combinatorics, algebraic geometry and perturbative quantum field theory. The standard recipe to study the asymptotic expansion of such sequences is to find a recurrence satisfied by them, convert it into a differential equation satisfied by their generating series, and analyze the singularities in the complex plane. We propose a shortcut by constructing directly from the structure of the hypergeometric term a finite set, for which we conjecture (and in some cases prove) that it contains all the singularities of the generating series. Our construction of this finite set is given by the solution set of a balanced system of polynomial equations of a rather special form, reminiscent of the Bethe ansatz. The finite set can also be identified with the set of critical values of a potential function, as well as with the evaluation of elements of an additive K-theory group by a regulator function. We give a proof of our conjecture in some special cases, and we illustrate our results with numerous examples.