The d-ary Sidel'nikov sequence S = s0, s1 … of period q - 1 for a prime power q = pm is a frequently analyzed sequence in the literature. Recently, it turned out that the linear complexity over Fp of the d-ary Sidel'nikov sequence is considerably smaller than the period if the sequence element s( q - 1) /2 mod (q - 1) is chosen adequately. In this paper this work is continued and tight lower bounds on the linear complexity over Fp of the d-ary Sidel'nikov sequence are given. For certain cases exact values are provided. Finally, results on the k-error linear complexity over Fp of the d-ary Sidel'nikov sequence are presented. [ABSTRACT FROM AUTHOR]
The central issue in this paper is to transmit a quantum state in such a way that after some decoherence occurs, most of the information can be restored by a suitable decoding operation. For this purpose, we incorporate redundancy by mapping a given initial quantum state to a messenger state on a larger dimensional Hilbert space via a C* -algebra embedding. Our noise model for the transmission is a phase damping channel which admits a noiseless subsystem or decoherence-free subspace. More precisely, the transmission channel is obtained from convex combinations of a set of lowest rank yes/no measurements that leave a component of the messenger state unchanged. The objective of our encoding is to distribute quantum information optimally across the noise-susceptible component of the transmission when the noiseless component is not large enough to contain all the quantum information to be transmitted. We derive simple geometric conditions for optimal encoding and construct examples of such encodings. [ABSTRACT FROM AUTHOR]
The filter generator is an important building block in many stream ciphers. The generator consists of a linear feedback shift register of length n that generates an m-sequence of period 2′ - 1 filtered through a Boolean function of degree d that combines bits from the shift register and creates an output bit zt at any time t. The previous best attacks aimed at reconstructing the initial state from an observed keystream, have essentially reduced the problem to solving a nonlinear system of D = (Multiple line equation(s) cannot be represented in ASCII text) (i) equations in n unknowns using techniques based on linear algebra. This attack needs about D bits of keystream and the system can be solved in complexity O (Dω), where ω can be taken to be Strassen's reduction exponent ω = log2 (7) ≈ 2.807. This paper describes a new algorithm that recovers the initial state of most filter generators after observing O(D) keystream bits with complexity O((D - n)/2) ≈ O(D), after a pre-computation with complexity O(D(log2 D)³). [ABSTRACT FROM AUTHOR]