zbMATH — the first resource for mathematics

Linear complexity and random sequences. (English) Zbl 0654.68044
Advances in cryptology - EUROCRYPT ’85, Proc. Workshop, Linz/Austria 1985, Lect. Notes Comput. Sci. 219, 167-188 (1986).
Summary: The problem of characterizing the randomness of finite sequences arises in cryptographic applications. The idea of randomness clearly reflects the difficulty of predicting the next digit of a sequence from all the previous ones. The approach taken in this paper is to measure the (linear) unpredictability of a sequence (finite or periodic) by the length of the shortest linear feedback shift register (LFSR) that is able to generate the given sequence. This length is often referred to in the literature as the linear complexity of the sequence. It is shown that the expected linear complexity of a sequence of \(n\) independent and uniformly distributed binary random variables is very close to \(n/2\) and, that the variance of the linear complexity is virtually independent of the sequence length, i.e. is virtually a constant! For the practically interesting case of periodically repeating a finite truly random sequence of length \(2^m\) or \(2^m-1\), it is shown that the linear complexity is close to the period length.

[For the entire collection see Zbl 0583.00050.]

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
94A60 Cryptography
Full Text: DOI