Namespaces
Variants
Actions

Difference between revisions of "Linear complexity of a sequence"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (AUTOMATIC EDIT (latexlist): Replaced 46 formulas out of 46 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
(latex details)
 
Line 7: Line 7:
  
 
{{TEX|semi-auto}}{{TEX|done}}
 
{{TEX|semi-auto}}{{TEX|done}}
For a [[Shift register sequence|shift register sequence]] $\mathbf{a}$, the linear complexity $L ( \mathbf{a} )$ is just the degree of its minimal polynomial $m$, i.e. the length of a shortest linear feedback shift register (LFSR; cf. [[Shift register sequence|Shift register sequence]]) capable of producing $\mathbf{a}$. The linear complexity also equals the maximum number of linearly independent vectors among the state vectors
+
For a [[shift register sequence]] $\mathbf{a}$, the linear complexity $L ( \mathbf{a} )$ is just the degree of its minimal polynomial $m$, i.e. the length of a shortest linear feedback shift register (LFSR; cf. [[Shift register sequence|Shift register sequence]]) capable of producing $\mathbf{a}$. The linear complexity also equals the maximum number of linearly independent vectors among the state vectors
  
 
\begin{equation*} {\bf a}^ { ( t ) } = ( a _ { t } , a _ { t  + 1} , \dots , a _ { n + t - 1 }) ( t \geq 0 ) \end{equation*}
 
\begin{equation*} {\bf a}^ { ( t ) } = ( a _ { t } , a _ { t  + 1} , \dots , a _ { n + t - 1 }) ( t \geq 0 ) \end{equation*}
Line 13: Line 13:
 
of an arbitrary LFSR of length $n$ associated with $\mathbf{a}$.
 
of an arbitrary LFSR of length $n$ associated with $\mathbf{a}$.
  
Now, let $\mathbf{a}$ denote either a finite sequence $( a _ { k } ) _ { k  = 0 , \dots , N - 1}$ of length $N$ or an infinite sequence $( a _ { k } ) _ { k  \geq 0}$ over a [[Galois field|Galois field]] ${F} = \operatorname{GF} ( q )$ (in the latter case, put $N = \infty$). For every positive integer $k < N$, denote by $L _ { k } ( \mathbf{a} )$ the length of an LFSR $\Lambda _ { k } ( \mathbf{a} )$ of least length over $F$ capable of producing a shift register sequence ${\bf s} ^ { ( k ) }$ which agrees with $\mathbf{a}$ for the first $k$ entries $a _{0} , \dots , a _ { k - 1 }$. In this way, one obtains a sequence $\mathbf{L} = ( L _ { k } ( \mathbf a ) )$ of the same length $N$, which is called the linear complexity profile of $\mathbf{a}$. Then one defines the linear complexity $L ( \mathbf{a} )$ of $\mathbf{a}$ as the maximum value of all $L _ { k } ( \mathbf{a} )$ if these values are bounded, and as $\infty$ otherwise. Thus, $L ( \mathbf{a} ) = \infty$ if and only if $\mathbf{a}$ is an infinite sequence which is not ultimately periodic (cf. [[Ultimately periodic sequence|Ultimately periodic sequence]]), and $L ( \mathbf{a} ) = L _ { N } ( \mathbf{a} )$ if $\mathbf{a}$ is a finite sequence of length $N$. Hence the linear complexity profile constitutes a refinement of the linear complexity of a sequence. The linear complexity profile of $\mathbf{a}$ and the associated sequence of LFSRs $\Lambda _ { k } ( \mathbf{a} )$ can be computed efficiently by the celebrated [[Berlekamp–Massey algorithm|Berlekamp–Massey algorithm]], see [[#References|[a1]]] or [[#References|[a2]]].
+
Now, let $\mathbf{a}$ denote either a finite sequence $( a _ { k } ) _ { k  = 0 , \dots , N - 1}$ of length $N$ or an infinite sequence $( a _ { k } ) _ { k  \geq 0}$ over a [[Galois field|Galois field]] ${F} = \operatorname{GF} ( q )$ (in the latter case, put $N = \infty$). For every positive integer $k<N$, denote by $L _ { k } ( \mathbf{a} )$ the length of an LFSR $\Lambda _ { k } ( \mathbf{a} )$ of least length over $F$ capable of producing a shift register sequence ${\bf s} ^ { ( k ) }$ which agrees with $\mathbf{a}$ for the first $k$ entries $a _{0} , \dots , a _ { k - 1 }$. In this way, one obtains a sequence $\mathbf{L} = ( L _ { k } ( \mathbf a ) )$ of the same length $N$, which is called the linear complexity profile of $\mathbf{a}$. Then one defines the linear complexity $L ( \mathbf{a} )$ of $\mathbf{a}$ as the maximum value of all $L _ { k } ( \mathbf{a} )$ if these values are bounded, and as $\infty$ otherwise. Thus, $L ( \mathbf{a} ) = \infty$ if and only if $\mathbf{a}$ is an infinite sequence which is not ultimately periodic (cf. [[Ultimately periodic sequence|Ultimately periodic sequence]]), and $L ( \mathbf{a} ) = L _ { N } ( \mathbf{a} )$ if $\mathbf{a}$ is a finite sequence of length $N$. Hence the linear complexity profile constitutes a refinement of the linear complexity of a sequence. The linear complexity profile of $\mathbf{a}$ and the associated sequence of LFSRs $\Lambda _ { k } ( \mathbf{a} )$ can be computed efficiently by the celebrated [[Berlekamp–Massey algorithm|Berlekamp–Massey algorithm]], see [[#References|[a1]]] or [[#References|[a2]]].
  
The linear complexity of a sequence is an important aspect in judging its suitability for use in [[Cryptography|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 [[#References|[a3]]], Chap. 4, where it is shown that a binary random sequence $\mathbf{a}$ of length $N$ usually has linear complexity very close to $N / 2$ with the complexity profile growing in a roughly (but not exactly!) continuous manner (so that $L _ { k } ( \mathbf{a} )$ is close to $k / 2$). Moreover, using $\mathbf{a}$ to generate a periodic sequence $\mathbf{s}$ with period $N$ results in a linear complexity close to $N$, provided that $N$ is a power of $2$ or a Mersenne prime number (cf. [[Mersenne number|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.
+
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 [[#References|[a3]]], Chap. 4, where it is shown that a binary random sequence $\mathbf{a}$ of length $N$ usually has linear complexity very close to $N / 2$ with the complexity profile growing in a roughly (but not exactly!) continuous manner (so that $L _ { k } ( \mathbf{a} )$ is close to $k / 2$). Moreover, using $\mathbf{a}$ to generate a periodic sequence $\mathbf{s}$ with period $N$ results in a linear complexity close to $N$, provided that $N$ is a power of $2$ 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====
 
====References====
<table><tr><td valign="top">[a1]</td> <td valign="top"> R.E. Blahut,   "Theory and practice of error control codes" , Addison-Wesley (1983)</td></tr><tr><td valign="top">[a2]</td> <td valign="top"> D. Jungnickel,   "Finite fields: Structure and arithmetics" , Bibliographisches Inst. Mannheim (1993)</td></tr><tr><td valign="top">[a3]</td> <td valign="top"> R. Rueppel,   "Analysis and design of stream ciphers" , Springer (1986)</td></tr></table>
+
<table>
 +
<tr><td valign="top">[a1]</td><td valign="top"> R.E. Blahut, "Theory and practice of error control codes", Addison-Wesley (1983)</td></tr>
 +
<tr><td valign="top">[a2]</td><td valign="top"> D. Jungnickel, "Finite fields: Structure and arithmetics", Bibliographisches Inst. Mannheim (1993)</td></tr>
 +
<tr><td valign="top">[a3]</td><td valign="top"> R. Rueppel, "Analysis and design of stream ciphers", Springer (1986)</td></tr>
 +
</table>

Latest revision as of 19:04, 17 February 2024

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

\begin{equation*} {\bf a}^ { ( t ) } = ( a _ { t } , a _ { t + 1} , \dots , a _ { n + t - 1 }) ( t \geq 0 ) \end{equation*}

of an arbitrary LFSR of length $n$ associated with $\mathbf{a}$.

Now, let $\mathbf{a}$ denote either a finite sequence $( a _ { k } ) _ { k = 0 , \dots , N - 1}$ of length $N$ or an infinite sequence $( a _ { k } ) _ { k \geq 0}$ over a Galois field ${F} = \operatorname{GF} ( q )$ (in the latter case, put $N = \infty$). For every positive integer $k<N$, denote by $L _ { k } ( \mathbf{a} )$ the length of an LFSR $\Lambda _ { k } ( \mathbf{a} )$ of least length over $F$ capable of producing a shift register sequence ${\bf s} ^ { ( k ) }$ which agrees with $\mathbf{a}$ for the first $k$ entries $a _{0} , \dots , a _ { k - 1 }$. In this way, one obtains a sequence $\mathbf{L} = ( L _ { k } ( \mathbf a ) )$ of the same length $N$, which is called the linear complexity profile of $\mathbf{a}$. Then one defines the linear complexity $L ( \mathbf{a} )$ of $\mathbf{a}$ as the maximum value of all $L _ { k } ( \mathbf{a} )$ if these values are bounded, and as $\infty$ otherwise. Thus, $L ( \mathbf{a} ) = \infty$ if and only if $\mathbf{a}$ is an infinite sequence which is not ultimately periodic (cf. Ultimately periodic sequence), and $L ( \mathbf{a} ) = L _ { N } ( \mathbf{a} )$ if $\mathbf{a}$ is a finite sequence of length $N$. Hence the linear complexity profile constitutes a refinement of the linear complexity of a sequence. The linear complexity profile of $\mathbf{a}$ and the associated sequence of LFSRs $\Lambda _ { k } ( \mathbf{a} )$ 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 $\mathbf{a}$ of length $N$ usually has linear complexity very close to $N / 2$ with the complexity profile growing in a roughly (but not exactly!) continuous manner (so that $L _ { k } ( \mathbf{a} )$ is close to $k / 2$). Moreover, using $\mathbf{a}$ to generate a periodic sequence $\mathbf{s}$ with period $N$ results in a linear complexity close to $N$, provided that $N$ is a power of $2$ 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=55539
This article was adapted from an original article by Dieter Jungnickel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article