Namespaces
Variants
Actions

Linear complexity of a sequence

From Encyclopedia of Mathematics
Revision as of 17:12, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

For a shift register sequence , the linear complexity is just the degree of its minimal polynomial , i.e. the length of a shortest linear feedback shift register (LFSR; cf. Shift register sequence) capable of producing . The linear complexity also equals the maximum number of linearly independent vectors among the state vectors

of an arbitrary LFSR of length associated with .

Now, let denote either a finite sequence of length or an infinite sequence over a Galois field (in the latter case, put ). For every positive integer , denote by the length of an LFSR of least length over capable of producing a shift register sequence which agrees with for the first entries . In this way, one obtains a sequence of the same length , which is called the linear complexity profile of . Then one defines the linear complexity of as the maximum value of all if these values are bounded, and as otherwise. Thus, if and only if is an infinite sequence which is not ultimately periodic (cf. Ultimately periodic sequence), and if is a finite sequence of length . Hence the linear complexity profile constitutes a refinement of the linear complexity of a sequence. The linear complexity profile of and the associated sequence of LFSRs can be computed efficiently by the celebrated Berlekamp–Massey algorithm, see [a1] or [a2].

The linear complexity of a sequence is an important aspect in judging its suitability for use in cryptography. A high linear complexity by itself does not guarantee any randomness properties of the sequence considered. The linear complexity profiles of binary random sequences are analyzed in [a3], Chap. 4, where it is shown that a binary random sequence of length usually has linear complexity very close to with the complexity profile growing in a roughly (but not exactly!) continuous manner (so that is close to ). Moreover, using to generate a periodic sequence with period results in a linear complexity close to , provided that is a power of or a Mersenne prime number (cf. Mersenne number). Consequently, a periodic binary sequence with good randomness properties should have complexity close to the period length and a profile growing more or less smoothly.

References

[a1] R.E. Blahut, "Theory and practice of error control codes" , Addison-Wesley (1983)
[a2] D. Jungnickel, "Finite fields: Structure and arithmetics" , Bibliographisches Inst. Mannheim (1993)
[a3] R. Rueppel, "Analysis and design of stream ciphers" , Springer (1986)
How to Cite This Entry:
Linear complexity of a sequence. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Linear_complexity_of_a_sequence&oldid=50134
This article was adapted from an original article by Dieter Jungnickel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article