A Survey on Complexity Measures for Pseudo-Random Sequences

Abstract

Since the introduction of the Kolmogorov complexity of binary sequences in the 1960s, there have been significant advancements on the topic of complexity measures for randomness assessment, which are of fundamental importance in theoretical computer science and of practical interest in cryptography. This survey reviews notable research from the past four decades on the linear, quadratic and maximum-order complexities of pseudo-random sequences, and their relations with Lempel–Ziv complexity, expansion complexity, 2-adic complexity and correlation measures.

1. Introduction

Cryptography and security applications make extensive use of random bits, such as keys and initialization vectors in encryption and nonces in security protocols. The generation of random bits should be designed with the security goal of indistinguishability from an ideal randomness source, which generates identically distributed and independent uniform random bits with full entropy (i.e., one bit of entropy per bit). However, this security goal is challenging to achieve. The list of real-world failures, where a random bit generator (RBG) is broken and the security of the reliant application crumbles with it, continues to grow [1,2,3,4]. There are two fundamentally different strategies for designing RBGs. One strategy is to produce bits non-deterministically, where every bit of output is based on a physical process that is unpredictable; the other strategy is to compute bits deterministically using an algorithm from an initial value that contains sufficient entropy to provide an assurance of randomness. This class of RBG is referred to as pseudo-random bit generators (PRBGs) or deterministic random bit generators (DRBGs) [5]. Due to their deterministic nature, PRBGs produce sequences of pseudo-random (rather than random) bits. Real-world PRBGs usually employ cryptographic primitives, such as stream ciphers, block ciphers, hash functions and elliptic curves, as their basic building blocks. For instance, the revised NIST SP 800-90A standard [5] recommends Hash-DRBG, HMAC-DRBG and CTR-DRBG based on approved hash functions and block ciphers. It is worth mentioning that, as pointed out in [2], the NIST SP 800-90A standard is not free from controversy: the disgraced algorithm DualEC-DRBG in the standard was reported to contain a back door [3]; the recommended DRBGs, when supporting a variety of optional inputs and parameters, do not fit cleanly into the usual security models of PRBGs; there is no formal competition in the standarization process; and there is a limited amount of formal analysis of the recommended DRBGs.Although not included in the NIST standard, PRBGs that use stream ciphers based on feedback shift registers (FSRs) as building blocks have several advantages, including the simple structure of operations of addition and multiplication, fast and easy hardware implementations in almost all computing devices, and good statistic characteristics (long period, balance, run properties, etc.) in output sequences [6,7]. In addition, the output sequence from other PRBGs will ultimately become periodic and therefore can be produced by certain FSRs. This provides another perspective for investigating the security strength of output sequences from PRBGs.

Consider a pseudo-random sequence $\mathbf{s}=s_0{s}_1{s}_2\dots$ generated from a PRBG. A natural question arises: how should one evaluate the randomness of the sequence $\mathbf{s}$? Research on this problem can be traced back to the early 20th century. As early as 1919, Mises [8] initiated the notion of random sequences based on his frequency theory of probability. Later, Church [9] pointed out the vagueness of the second condition on randomness in [8] and proposed a less restricted but more precise definition of random sequences, as follows: An infinite binary sequence $\mathbf{s}$ is a random sequence if it satisfies the following two conditions: (1) assume $f(r,\mathbf{s})$ denotes the number of 1s among the first r terms of $\mathbf{s}$, then the sequence $f(r,\mathbf{s})/r$ for $\mathbf{s}$ approaches a limit p as r approaches infinity; (2) for a sequence $\mathbf{b}$ with $b_1=1,b_{n+1}=2b_n+s_n$ and any effectively calculable function $\varphi$, if the integers n such that $\varphi \left(b_n\right)=1$ form an infinite sequence $n_1,n_2,\cdots$, then the sequence $f(r,\mathbf{c})/r$ for $\mathbf{c}=s_{n_1}{s}_{n_2}{s}_{n_3}\dots$ approaches the same limit p as r approaches infinity. Despite the emphasis of calculability of $\varphi$ in Condition (2), one can see that it is hardly (if not at all) possible to test the randomness of a sequence by this definition. It could be used in randomness test by negative outcomes, namely, a binary sequence $\mathbf{s}$ is not random if one can find certain effectively calculable function $\varphi$, for which Condition (2) cannot hold. In order to justify a proposed definition of randomness, one has to show that the sequences, which are random in the stated sense, possess various properties of stochasticity with which we are acquainted in probability theory. Inspired by the properties obeyed by the maximum-length sequences, Golomb proposed the randomness postulates of binary sequences [10]: balancedness, run property (a subsequence of consecutive 1 s/0 s in a sequence is termed a run. A maximum-length sequence of length $2^m-1$ contains one run of m 1 s, one run of $(m-1)$ 0 s and $2^k$ runs of $m-2-k$ 1 s and 0 s for $k=0,1,\dots ,m-3$) and ideal autocorrelation. Kolmogorov [11] proposed the notion of complexity to test the randomness of a sequence $\mathbf{s}$, which is defined as ${min}_{A\left(\mathbf{x}\right)=\mathbf{s}}\mathrm{len}\left(\mathbf{x}\right)$, the length of the shortest $\mathbf{x}$ that can produce $\mathbf{s}$ by a universal Turing machine program A. This notion is later referred to as the Kolmogorov complexity in the literature. Along this line, further developments were made in [12,13] and summarized in Knuth’s famous book series The Art of Computer Programming [14].

Rather than considering an abstract Turing machine program that generates a given sequence, the model of using FSRs to generate a given sequence has attracted considerable attention. This model has two major advantages: firstly, all sequences that are generated by a finite-state machine in a deterministic manner are ultimately periodic, and as such, can be produced by certain finite-state shift registers; secondly, it is comparatively easier and more efficient to identify the shortest FSRs producing a given sequence, either of a finite length or of infinite length with a certain period. Due to its tractability, the linear complexity of a specific sequence $\mathbf{s}$, which uses linear FSRs (LFSRs) as the algorithm A in the Kolmogorov complexity, is particularly appealing and has been intensively studied. The linear complexity of a given sequence $\mathbf{s}$ can be efficiently calculated by the Berlekamp–Massey algorithm [15,16], and the stochastic behavior of linear complexity for finite-length sequences and periodic sequences can be considered to be fairly well understood [17,18,19]. The good understanding of linear complexity of sequences is an important factor for its adoption in the NIST randomness test suite [20]. Note that extremely long sequences with large linear complexity can usually be generated by much short FSRs with certain nonlinear feedback function. Consequently, more figures of merit to judge the randomness of sequences, such as maximum-order complexity [21], 2-adic complexity [22], quadratic complexity [23], expansion complexity [24] and their variants, have been also explored in the literature.

This paper will survey the development of complexity measures used to assess the randomness of sequences. It is important to note that this paper does not intend to offer a comprehensive survey of this broad topic. Instead, it aims to provide a preliminary overview of the topic with technical discussions to certain extent, focusing mainly on complexities within the domain of FSR that align with the author’s research interests. To this end, I delved into significant findings on the study of FSR-based complexity measures, particularly on the algorithmic and algebraic methods in computation, statistical behavior, theoretical constructions and the relations of those complexity measures. Research papers on this topic presented at flagship conferences in cryptography, such as ASIACRYPT, CRYPTO and EUROCRYPT, published at prestigious journals with IEEE, Springer, Science Direct, etc, as well as some well-recognized books since the 1970s constitute the major content of this survey. Readers may refer to relevant surveys on this topic with different focuses by Meidl and Niederreiter [19,25] and Topuzoǧlus and Winterhof [26].

The remainder of this paper is organized as follows: Section 2 recalls the basics for feedback shift registers, which lays the foundation for the discussions in subsequent sections. Section 3 reviews important developments of the theory of linear complexity profile for random sequences, Section 4 discusses a mathematical tool used to efficiently calculate the quadratic complexity of sequences and Section 5 surveys computational methods, the statistical behavior for maximum-order complexity and theoretical constructions of periodic sequences with the largest maximum-order complexity. In Section 6, known relations among complexity measures of sequences are briefly summarized. Finally, conclusive remarks and discussion are given in Section 7.

2. Feedback Shift Registers

Let ${\mathbb{F}}_q$ be the finite field of q elements, where q is an arbitrary prime power. For a positive integer m, an m-stage feedback shift register (FSR) is a clock-controlled circuit consisting of m consecutive storage units and a feedback function f as displayed in Figure 1.

Starting with an initial state $s_0{s}_1\dots s_{m-1}$ over ${\mathbb{F}}_q$, the states in the FSR will be updated by a clock-controlled transformation as follows:

$$\mathcal{F}:s_i{s}_{i+1}\dots s_{i+m-1}⟼s_{i+1}\dots s_{i+m-1}{s}_{i+m},i\ge 0,$$

(1)

where

$$s_{i+m}=f(s_i,s_{i+1},\dots ,s_{i+m-1}),$$

and the leftmost symbol for each state will be output. In this way an FSR produces a sequence $\mathbf{s}=s_0{s}_1{s}_2\dots$ based on each initial state $s_0{s}_1\dots s_{m-1}$ and its feedback function f. The output sequence from an FSR, known as an FSR sequence, can be equivalently expressed as a sequence of states ${\underline{\mathbf{s}}}_i=s_i{s}_{i+1}\dots s_{i+m-1}$, with the relation ${\underline{\mathbf{s}}}_i=\mathcal{F}\left({\underline{\mathbf{s}}}_{i-1}\right)=\dots ={\mathcal{F}}^i\left({\underline{\mathbf{s}}}_0\right)$ for $i\ge 0$. When ${\underline{\mathbf{s}}}_p={\mathcal{F}}^p\left({\underline{\mathbf{s}}}_0\right)={\underline{\mathbf{s}}}_0$ for the least integer $p\ge 1$, we obtain a cycle of states ${\underline{\mathbf{s}}}_0,\dots {\underline{\mathbf{s}}}_{p-1}$, or equivalently a sequence $s_0\dots s_{p-1}\dots$ of least period p. In his influential book [10], Golomb intensively studied the properties of FSR sequences from both linear feedback functions and nonlinear feedback functions. Readers can refer to [10] for a comprehensive understanding of FSR sequences.

For an m-stage FSR with a feedback function f and an initial state $s_0{s}_1\dots s_{m-1}$, if we know n consecutive $s_i{s}_{i+1}\dots s_{i+n-1}$ in the output $\mathbf{s}$, then we obtain $n-m$ equations

$$\begin{array}{ccc}\hfill f(s_i,\dots ,s_{i+m-1})& =& s_{i+m}\hfill \\ \hfill f(s_{i+1},\dots ,s_{i+m})& =& s_{i+m+1}\hfill \\ \hfill & \dots & \\ \hfill f(s_{i+n-m-1},\dots ,s_{i+n-2})& =& s_{i+n-1}.\hfill \end{array}$$

(2)

When the feedback function f is linear, namely, $f(x_0,\dots ,x_{m-1})=a_1{x}_{m-1}+a_2{x}_{m-2}+\dots +a_m{x}_0$, and $n\ge 2m$, one can uniquely determine its m unknown coefficients $a_i$ from the above $n-m$ linear equations. When the feedback function f is nonlinear, the number of terms in f increases significantly. For instance, for $q=2$ a binary feedback function f of degree r has ${\sum }_{d=0}^r\left(\genfrac{}{}{0pt}{}{n}{d}\right)$ possible terms. The above equations in Equation (2) become more difficult to analyze. The equations are not necessarily linearly independent and a lot more variables are involved. Consequently, more observations and techniques are required in the analysis of these equations. In the following, we will review some results on FSR sequences when the feedback function is linear, quadratic and arbitrarily nonlinear, as well as their relations with other complexity measures.

We will consider both finite-length sequences and infinite-length sequences with certain finite period. Throughout what follows, we will use $\mathbf{s}$ to denote a generic sequence with terms from certain alphabet, ${\mathbf{s}}_n=s_0{s}_1\dots s_{n-1}$ to denote a sequence with length n that is not a repetition of any shorter sequence, ${\mathbf{s}}_n^k$ to denote a sequence of k repetition of ${\mathbf{s}}_n$ and ${\mathbf{s}}_n^{\infty }$ to denote infinite repetitions of ${\mathbf{s}}_n$, indicating that ${\mathbf{s}}_n^{\infty }$ has least period n.

3. Linear Complexity

Given an FSR, when its feedback function f is a linear function on the input state, namely, it is associated with the following linear recurrence:

$$s_{i+m}+a_1{s}_{i+m-1}+\cdots +a_{m-1}{s}_{i+1}+a_m{s}_i=0\mathrm{for}i=1,2,\dots ,$$

(3)

where $a_1,\dots ,a_m$ are taken from ${\mathbb{F}}_q$, it is termed linear FSR and the output sequence $\mathbf{s}$ is called an LFSR sequence of order m. The polynomial

$$f\left(x\right)=x^m+a_{m-1}{x}^{m-1}+\cdots +a_{1}x+a_0,$$

with $a_0=1$, is called the feedback or characteristic polynomial of $\mathbf{s}$. The zero sequence $00\dots$ is viewed as an LFSR sequence of order 0.

Definition 1.

Let $\mathbf{s}$ be an arbitrary sequence of elements of ${\mathbb{F}}_q$ and let n be a non-negative integer. Then the linear complexity $L_n\left(\mathbf{s}\right)$ is defined as the length of the shortest LFSR that can generate ${\mathbf{s}}_n=s_0{s}_1\dots s_{n-1}$. The sequence $L_0\left(\mathbf{s}\right),L_1\left(\mathbf{s}\right),L_2\left(\mathbf{s}\right),\dots ,$ is called the linear complexity profile of the sequence $\mathbf{s}$.

It is clear that $L_n\left(\mathbf{s}\right)\le L_{n+1}\left(\mathbf{s}\right)$ and $0\le L_n\left(\mathbf{s}\right)\le n$ for any integer n and sequence $\mathbf{s}$. Hence, the linear complexity profile of $\mathbf{s}$ is a nondecreasing sequence of non-negative integers. Two extreme cases for $L_n\left(\mathbf{s}\right)$ correspond to highly non-random sequences $\mathbf{s}$ whose first n elements $s_0{s}_1\dots s_{n-1}$ are either $\stackrel{n}{\overbrace{0\dots 0}}$ or $\stackrel{n-1}{\overbrace{0\dots 0}}{s}_{n-1}$ with $s_{n-1}\ne 0$, which has $L_n\left(\mathbf{s}\right)=0$ or $L_n\left(\mathbf{s}\right)=n$, respectively.

The linear complexity of a sequence $\mathbf{s}$ can be efficiently calculated by the well-known Berlekamp–Massey algorithm [15,16], which also returns the linear feedback function generating $\mathbf{s}$. In the Berlekamp–Massey algorithm, at each step $n-1$ with the current linear recurrence for $s_0{s}_1\dots s_{n-2}$, a discrepancy is calculated to assess whether the linear recurrence holds for the extended sequence $s_0{s}_1\dots s_{n-2}{s}_{n-1}$: when the discrepancy is zero, indicating that the current linear recurrence indeed holds for $s_0{s}_1\dots s_{n-2}{s}_{n-1}$, then move on to n; when the discrepancy is nonzero, indicating that a new (and possibly longer) linear recurrence is needed, the linear recurrence is then updated and the linear complexity is updated as

$$L_n\left(\mathbf{s}\right)=max\{L_{n-1}\left(\mathbf{s}\right),n-L_{n-1}\left(\mathbf{s}\right)\}.$$

(4)

Gustavson [27] showed that the above process requires $O\left(n^2\right)$ multiplication/addition operations for calculating $L_n\left(\mathbf{s}\right)$. Dornstetter, in [28], pointed out the equivalence between this procedure of calculation and the Euclidean algorithm.

Rueppel [17] investigated the varying behavior of the discrepancy ${\Delta }_t$, $1\le t<n$, for a binary sequence of length n, and characterized the linear complexity profile of random sequences in the following propositions.

Proposition 1.

The number of sequences of length n and linear complexity l, denoted by $N_n\left(l\right)$, satisfies the following recursive relation

$$N_n\left(l\right)=\left\{\begin{array}{cc}{N}_{n-1}\left(l\right),\hfill & 0\le l<\frac{n}{2},\hfill \\ 2N_{n-1}\left(l\right),\hfill & l=\frac{n}{2},\hfill \\ 2N_{n-1}\left(l\right)+N_{n-1}(n-l),\hfill & \frac{n}{2}<l<n,\hfill \end{array}\right.$$

and it, starting from $N_1\left(0\right)=N_1\left(1\right)=1$, can be given by

$$N_n\left(l\right)=\left\{\begin{array}{cc}{2}^{min\{2n-2l,2l-1\}},\hfill & 0<l\le n,\hfill \\ 1,\hfill & 0=l<n.\hfill \end{array}\right.$$

Proposition 2.

The expected linear complexity $L_n$ of binary random sequences of length n drawn from a uniform distribution is given by

$$E\left[L_n\right]=\frac{n}{2}+\frac{4+R_2\left(n\right)}{18}-2^{-n}\left(\frac{n}{3}+\frac{2}{9}\right),$$

and the variance of the linear complexity is given by

$$\begin{array}{cc}\hfill Var\left[L_n\right]& =\frac{86}{81}-2^{-n}\frac{3n(14-R_2\left(n\right))-(82-2R_2\left(n\right))}{81}-2^{-2n}\frac{9n^2+12n+4}{81},\hfill \end{array}$$

where $R_2\left(n\right)$ denotes n modulo 2.

From the above proposition, we readily see that

$$\underset{n\to \infty }{lim}E\left[L_n\right]=\frac{n}{2}+c_n\mathrm{and}\underset{n\to \infty }{lim}Var\left[L_n\right]=\frac{86}{81},$$

(5)

where $c_n=(4+R_2\left(n\right))/18.$ From Rueppel’s characterization on the general stochastic behavior of binary random sequences, a similar and more important question arose: for a randomly chosen and then fixed sequence $\mathbf{s}$ over ${\mathbb{F}}_q$, what is the behavior of $L_n\left(\mathbf{s}\right)$? To settle this question, Niederreiter [18] developed a probabilistic theory for linear complexity and linear complexity profiles of a given sequence $\mathbf{s}$ over any finite field ${\mathbb{F}}_q$. More specifically, he applied techniques from probability theory to dynamic systems and continued fractions, and deduced the probabilistic limit theorems for linear complexity by exploiting the connection between continued fractions and linear complexity of a sequence $\mathbf{s}$. Below we first recall the connection discussed in [18].

Given a sequence $\mathbf{s}=s_0{s}_1{s}_2\dots$, the fractional function $G\left(x\right)=s_0{x}^{-1}+s_1{x}^{-2}+s_2{x}^{-3}+\cdots \in {\mathbb{F}}_q\left[x^{-1}\right]$ has the following continued fraction expression

$$G=1/(A_1+1/(A_2+\cdots )),$$

where the partial quotients $A_1,A_2,\dots$ are polynomials over ${\mathbb{F}}_q$ with positive degrees. The n-th linear complexity of $\mathbf{s}$ can be expressed as

$$L_n\left(\mathbf{s}\right)=\sum _{i=1}^j{A}_i\left(\mathbf{s}\right)$$

for the integer j satisfying

$$\sum _{i=1}^{j-1}{A}_i\left(\mathbf{s}\right)+\sum _{i=1}^j{A}_i\left(\mathbf{s}\right)\le n\le \sum _{i=1}^j{A}_i\left(\mathbf{s}\right)+\sum _{i=1}^{j+1}{A}_i\left(\mathbf{s}\right).$$

By the study of the above continued fraction expansion, Niederreiter obtained the following result on $L_n\left(\mathbf{s}\right)$.

Theorem 1.

Suppose f is a non-negative nondecreasing function on the positive integers with ${\sum }_{n=1}^{\infty }{q}^{-f\left(n\right)}<\infty$. Then, we have

$$\left|L_n\left(\mathbf{s}\right)-\frac{n}{2}\right|\le \frac{1}{2}f\left(n\right)forallsufficientlylargen.$$

By taking $f\left(n\right)=(1+ϵ)logn/log\left(q\right)$ for arbitrary $ϵ>0$, a more explicit law of the logarithm for the n-th linear complexity of a random sequence $\mathbf{s}$ can be obtained as follows.

$$\begin{array}{cc}\hfill & \underset{n\to \infty }{\overline{lim}}\frac{L_n\left(\mathbf{s}\right)-\frac{n}{2}}{logn}=\frac{1}{2logq},\hfill \\ \hfill & \underset{n\to \infty }{\underline{lim}}\frac{L_n\left(\mathbf{s}\right)-\frac{n}{2}}{logn}=-\frac{1}{2logq}.\hfill \end{array}$$

(6)

Consequently, we have

$$L_n\left(\mathbf{s}\right)=\frac{n}{2}+O(log\left(n\right)).$$

(7)

As the equalities in (6) hold for infinitely many n, there is a strong interest in sequences $\mathbf{s}$ whose n-th linear complexity has small derivations from $n/2$.

Definition 2.

Let d be a positive integer. A sequence $\mathbf{s}=s_0{s}_1{s}_2\dots$ is said to be d-perfect if

$$\left|L_n\left(\mathbf{s}\right)-\frac{n}{2}\right|\le \frac{d}{2}foranyn\ge 1.$$

A 1-perfect sequence is also called perfect. A sequence is called almost perfect if it is d-perfect for some integer $d>1$.

Constructing d-perfect sequences is of significant interest. Sophisticated methods based on algebraic curves were introduced in [29], which yielded sequences with almost perfect linear complexity profiles. For cryptographic applications, especially as a keystream, a sequence $\mathbf{s}$ should have a linear complexity profile close to that of a random sequence. Moreover, this condition should be true for any starting point of the sequence. That is to say, for a sequence $\mathbf{s}=s_0{s}_1{s}_2\dots$ and any $r\ge 0$, the r-shifted sequence $s_r{s}_{r+1}{s}_{r+2}\dots$ should have an acceptable linear complexity profile close to random sequences as well. Niederreiter and Vielhaber [30] attacked this problem with the help of continued fractions. An important fact is that the jumps in the linear complexity profile of $\mathbf{s}$ are exactly the degrees of the partial quotients $A_1,A_2,\dots$. With such a connection, they proposed an algorithm to determine the linear complexity profile of shifted sequences $s_r{s}_{r+1}{s}_{r+2}\dots$ by investigating the corresponding continued fractions [31]. To be more concrete, they designed a method to calculate the continued fraction expansions of $G_n\left(x\right),\dots ,G_1\left(x\right)$, where $G_r\left(x\right)={\sum }_{j=r}^{n-1}{s}_j{x}^{-(j+1)}$ for $r\ge 0$. Later, in his survey paper [19], Niederreiter proposed the following open problem on d-perfect sequences.

Problem 1.

Construct a sequence $\mathbf{s}=s_0{s}_1{s}_2\dots$ over ${\mathbb{F}}_q$ such that the r-shifted sequences $s_r{s}_{r+1}{s}_{r+2}\dots$ for all $r\ge 0$ are d-perfect for some integer $d\ge 1$.

The preceding discussion is mainly concerned with generic infinite-length sequences. Note that sequences from an m-stage LFSR over ${\mathbb{F}}_q$ are periodic and their maximum period is $q^m-1$, which is achieved when the characteristic polynomial $f\left(x\right)$ is a primitive polynomial in ${\mathbb{F}}_q\left[x\right]$. LFSR sequences of order m with period $q^m-1$ are thus known as maximum-length sequences, or m-sequences for short. For a periodic sequence $\mathbf{s}={\mathbf{s}}_n^{\infty }$, the values in its linear complexity profile will remain unchanged at a certain point. This reveals apparently different linear complexity profiles between an infinite-length sequence of certain period and a random infinite-length sequence, which basically can be considered to have an arbitrarily long period.

An important tool for the analysis of the linear complexity of n-periodic sequences over ${\mathbb{F}}_q$ is the discrete Fourier transform. Assume $gcd(n,q)=1$, which means that there exists an n-th primitive root $\beta$ of unity in some finite extension of ${\mathbb{F}}_q$. Then the discrete Fourier transform of a time-domain n-tuple $\left(a_0,\dots ,a_{n-1}\right)\in {\mathbb{F}}_q^n$ is the (frequency-domain) n-tuple $\left(b_0,\dots ,b_{n-1}\right)$ with $b_j={\sum }_{i=0}^{n-1}{a}_i{\beta }^{ij}\mathrm{for}j=0,\dots ,n-1,$ i.e., 

$$\mathrm{DFT}\left((a_0,\dots ,a_{n-1})\right)=(a_0,\dots ,a_{n-1})\left(\begin{array}{cccc}1& \beta & \cdots & {\beta }^{n-1}\\ 1& {\beta }^2& \cdots & {\beta }^{2(n-1)}\\ ⋮& ⋮& \ddots & ⋮\\ 1& {\beta }^{n-1}& \cdots & {\beta }^{n-1(n-1)}\end{array}\right).$$

(8)

In this case, the linear complexity of an n-periodic sequence can be determined via the discrete Fourier transform [32].

Proposition 3.

Let $\mathbf{s}=s_0{s}_1{s}_2\dots$ be an n-periodic sequence over ${\mathbb{F}}_q$ with $gcd(n,q)=1$. Let β be an n-th primitive root of unity in an extension of ${\mathbb{F}}_q$ and $\left(b_0,\dots ,b_{n-1}\right)$ be the discrete Fourier transform of $(s_0,s_1,\dots s_{n-1})$ as in Equation (8). Then,

$$L_n\left(\mathbf{s}\right)=\#\{j:b_j\ne 0,0\le j<n\}=n-\#\left\{j:\sum _{i=0}^{n-1}{s}_i{\beta }^{ij}=0\right\}.$$

Massey and Serconek in [33] further extended the above relation to the general case $gcd(q,n)>1$ with the generalized discrete Fourier transform. The generalized discrete Fourier transform of $(s_0,s_1,\dots ,s_{n-1})$, where $n=p^{v}w$, $gcd(w,p)=1$ and p is the characteristic of ${\mathbb{F}}_q$, is defined as the following $p^v\times n$ matrix

$$GDFT\left((s_0,s_1,\dots ,s_{n-1})\right)=\left(\begin{array}{cccc}s\left(1\right)& s\left(\beta \right)& \cdots & s\left({\beta }^{n-1}\right)\\ s^{\left[1\right]}\left(1\right)& s^{\left[1\right]}\left(\beta \right)& \cdots & s^{\left[1\right]}\left({\beta }^{n-1}\right)\\ ⋮& & & \\ s^{\left[p^v-1\right]}\left(1\right)& s^{\left[p^v-1\right]}\left(\beta \right)& \cdots & s^{\left[p^v-1\right]}\left({\beta }^{n-1}\right)\end{array}\right)$$

where $\beta$ is any n-th primitive root of unity over ${\mathbb{F}}_q$ and

$$s^{\left[t\right]}\left(x\right)=\sum _{i=0}^{n-1}\left(\genfrac{}{}{0pt}{}{i}{t}\right)s_i{x}^{i-t}$$

is the t-th Hasse derivative of the polynomial $s_0+s_{1}x+\cdots +s_{n-1}{x}^{n-1}$. It is clear that when $gcd(n,q)=1$, the GDFT of $(s_0,s_1,\dots ,s_{n-1})$ reduced to the discrete Fourier transform of $(s_0,s_1,\dots ,s_{n-1})$. As pointed out in [33,34], the linear complexity of $\mathbf{s}={\mathbf{s}}_n^{\infty }$ can be calculated in terms of the Günther weight of $GDFT\left((s_0,s_1,\dots ,s_{n-1})\right)$, which was referred to as the Günther–Blahut theorem, which was used by Blahut implicitly in [35].

Proposition 4.

Let $\mathbf{s}={\mathbf{s}}_n^{\infty }$ be an n-periodic sequence over ${\mathbb{F}}_q$ with characteristic p, where $n=p^{v}w$ with $gcd(w,p)=1$. Then, the linear complexity of $\mathbf{s}$ is equal to the Günther weight of the GDFT of the n-tuple $(s_0,s_1,\dots ,s_{n-1})$, where the Günther weight of a matrix M is the number of its entries that are nonzero.

Algebraically, the linear complexity of ${\mathbf{s}}_n^{\infty }$ can be obtained via the feedback polynomial of the LFSR generating $\mathbf{s}$ [36]. Consider the generating function

$$g\left(x\right)=\sum _{i=0}^{\infty }{s}_i{x}^i=\frac{s_0+s_{1}x+\cdots +s_{n-1}{x}^{n-1}}{1-x^n}.$$

Assume the characteristic polynomial of $\mathbf{s}$ is given by $f\left(x\right)=x^m+a_{m-1}{x}^{m-1}+\cdots +a_{1}x+a_0$ with $a_0=1$. Then

$$\begin{array}{cc}\hfill f\left(x\right)g\left(x\right)& =s_0+(s_1+a_1{s}_0)x+\cdots +(s_{m-1}+a_1{s}_{m-2}+\cdots +a_{m-1}{s}_0)x^{m-1}\hfill \\ & +\sum _{i\ge 0}(s_{i+m}+a_1{s}_{i+m-1}+\cdots +a_m{s}_i)x^{i+m}\hfill \\ & =s_0+(s_1+a_{m-1}{s}_0)x+\cdots +(s_{m-1}+a_{m-1}{s}_{n-2}+\cdots +a_1{s}_0)x^{m-1}.\hfill \end{array}$$

Letting $\phi \left(x\right)=-f\left(x\right)g\left(x\right)$, we have

$$g\left(x\right)=-\frac{\phi \left(x\right)}{f\left(x\right)}=-\frac{{\phi }_0\left(x\right)}{f_0\left(x\right)},$$

where $gcd({\phi }_0,f_0)=1$ and $f_0$ is the minimal polynomial of $\mathbf{s}$. This relation implies the following equality [36]:

$$f_0\left(x\right)s_n\left(x\right)=(x^n-1){\phi }_0\left(x\right).$$

where $s_n\left(x\right)=s_0+s_{1}x+\cdots +s_{n-1}{x}^{n-1}$. Since $gcd({\phi }_0,f_0)=1$, it follows that $f_0\left(x\right)|(x^n-1)$ and ${\phi }_0\left(x\right)|s_n\left(x\right)$. Therefore, we have the following result.

Proposition 5.

Let $\mathbf{s}={\mathbf{s}}_n^{\infty }$ be an n-periodic sequence over ${\mathbb{F}}_q$ and $s\left(x\right)$ be the associated function of $\mathbf{s}$ given by $s_n\left(x\right)=s_0+s_{1}x+\cdots +s_{n-1}{x}^{n-1}$. Then the minimal polynomial of $\mathbf{s}$ is given by

$$f_0\left(x\right)=\frac{x^n-1}{gcd(x^n-1,s_n\left(x\right))},$$

indicating that

$$L\left(\mathbf{s}\right)=n-deg(gcd(x^n-1,s_n\left(x\right))).$$

With the above neat expression of $L\left(\mathbf{s}\right)$ for periodic sequences ${\mathbf{s}}_n^{\infty }$, several families of sequences with a nice algebraic structure were investigated, such as Legendre sequences [37], discrete logarithm function [38], Lempel–Cohn–Eastman sequences [39]. For more information about linear complexity of sequences with special algebraic structures, readers are referred to Shparlinski’s book [40].

The above discussion is concerned with the explicit calculation of an n-periodic sequence. The statistical behavior of a random n-periodic sequence over ${\mathbb{F}}_q$ is of fundamental interest, particularly from the cryptographic perspective. Rueppel in [41] considered this problem: if we let $\mathbf{s}={\mathbf{s}}_n^{\infty }$ run through all n-periodic sequences over ${\mathbb{F}}_q$, what is the expected linear complexity of

$$E_{q,n}=\frac{1}{q^n}\sum _{\mathbf{s}}L\left(\mathbf{s}\right)?$$

For the case $q=2$, Rueppel showed that if n is a power of 2, then $E_{2,n}=n-1+2^{-n};$ and if $n=2^m-1$ with a prime m, then $E_{2,n}⪆e^{-\frac{1}{n}}\left(n-\frac{1}{2}\right)$. Based on observations on numerical results, he conjectured that $E_{2,n}$ is always close to n. There was little progress on this conjecture until the work by Meidl and Niederreiter [42], in which they studied $E_{q,n}$ for an arbitrary prime power q with the help of the above Günther–Blahut theorem and the analysis of cyclotomic cosets. For an integer $0\le j<w$, the cyclotomic coset of j modulo w is defined as $C_j=\{j{q}^t(modw):t\ge 0\}$.

Theorem 2.

Let $n=p^{v}w$, where p is the characteristic of ${\mathbb{F}}_q,v\ge 0$ and $gcd(p,w)=1$. Let $C_1,\dots ,C_h$ be the different cyclotomic cosets modulo w and $b_i=\left|C_i\right|$ for $1\le i\le h$. Then

$$E_{q,n}=n-\sum _{i=1}^h\frac{b_i\left(1-q^{-b_i{p}^v}\right)}{q^{b_i}-1}.$$

From Theorem 2, a routine inequality scaling

$$\sum _{i=1}^h\frac{b_i\left(1-q^{-b_i{p}^v}\right)}{q^{b_i}-1}<\sum _{i=1}^h\frac{b_i}{q^{b_i}-1}<\frac{1}{q-1}\sum _{i=1}^h{b}_i=\frac{w}{q-1}$$

implies that

$$E_{q,n}\ge n-\frac{w}{q-1}.$$

In the particular case $v=0$,

$$E_{q,n}\ge n-\frac{w}{q-1}=n(1-\frac{1}{q-1}).$$

For small q, the above lower bounds can be further improved. For instance, for $q=2$, as the only singleton coset is $C_0=\left\{0\right\}$, it follows that

$$E_{2,n}\ge \left\{\begin{array}{c}n-\frac{w-2}{3}\mathrm{for}\mathrm{any}n,\hfill \\ \frac{3n-1}{4}\mathrm{for}\mathrm{odd}n.\hfill \end{array}\right.$$

Recall that the expected linear complexity of a random binary sequence $s_0{s}_1\dots s_{n-1}$ is around $\frac{n}{2}$. For a periodic sequence $\mathbf{s}={\mathbf{s}}_n^{\infty }$ from a sequence ${\mathbf{s}}_n$ with linear complexity l, the calculation of linear complexity of ${\mathbf{s}}_n^{\infty }$ needs to consider the sequence $s_0{s}_1\dots s_{n-1}{s}_0\dots s_{l-1}$. This expansion sequence, when considered as a random sequence, would have expected complexity around $(n+l)/2$. This is somewhat consistent with $E_{2,n}=(3n-1)/4$ when $l=(n-1)/2$ for odd n. Further improved results for the case $gcd(q,n)=1$ were obtained by more detailed analysis and can be found in [42].

4. Quadratic Complexity

Quadratic feedback functions are the easiest nonlinear case and has been discussed by some researchers [43,44,45]. Chan and Games, in [43], studied the quadratic complexity of binary DeBruijn sequences of order m (in which each binary string $s_0{s}_1\dots s_{m-1}$ appears exactly once); Youssef and Gong characterized a jump property of the quadratic complexity profile of random sequences, and Rizomiliotis et al., in [45], proposed an efficient method to calculate the quadratic complexity of binary sequences in general. We first recall the definition of quadratic complexity of a sequence in the following:

Definition 3.

Given a binary sequence $\mathbf{s}=s_0{s}_1{s}_2\dots$, its quadratic complexity is the length of the shortest FSRs with quadratic feedback functions

$$f(x_0,x_1,\dots ,x_{m-1})=\sum _{0\le i,j<m}{a}_{i,j}{x}_i{x}_j+\sum _{0\le i<m}{a}_i{x}_i+a,a_{i,j},a_i,a\in {\mathbb{F}}_2$$

that can generate $\mathbf{s}$. The quadratic complexity profile of the sequence $\mathbf{s}$ is similarly defined as $Q_0\left(\mathbf{s}\right),Q_1\left(\mathbf{s}\right),Q_2\left(\mathbf{s}\right),\dots$, where $Q_n\left(\mathbf{s}\right)$ is the quadratic complexity of the first n terms of $\mathbf{s}$.

For the first n terms $s_0{s}_1\dots s_{n-1}$ of $\mathbf{s}$, suppose it can be generated by an m-stage quadratic FSR. Following the recurrence as in Equation (2), we can obtain a system of $n-m$ equations. More concretely, denote

$$\begin{array}{cc}\hfill F\left(m\right)& ={(a,a_0,\overbrace{a_1,a_{0,1}},\overbrace{a_2,a_{1,2},a_{0,2}},\dots ,\overbrace{a_{m-1},a_{m-2,m-1},\dots ,a_{0,m-1}})}^T,\hfill \\ \hfill E(n,m)& ={(s_m,s_{m+1},\dots ,s_{n-1})}^T,\hfill \\ \hfill M(n,m)& =\left({\mathbf{1}}_{n-m}^T\right|B_0(m,n)|\dots |B_{m-1}(n,m)),\hfill \end{array}$$

where, for $0\le i<m$,

$$B_i(n,m)=\left(\begin{array}{cccc}{s}_i& s_i{s}_{i-1}& \cdots & s_i{s}_0\\ s_{i+1}& s_{i+1}{s}_i& \cdots & s_{i+1}{s}_1\\ ⋮& ⋮& & ⋮\\ s_{i+k-1}& s_{i+k-1}{s}_{i+k-2}& \cdots & s_{i+k-1}{s}_{k-1}\end{array}\right).$$

with $k=n-m$. According to the ordering in $F\left(m\right)$ and $M(n,m)$, it is easy to verify that

$$M(n,m)F\left(m\right)=E(n,m).$$

(9)

Therefore, finding a quadratic feedback function in m variables that outputs the sequence ${\mathbf{s}}_n=s_0{s}_1\dots s_{n-1}$ is equivalent to solving the above system of linear equations in $1+\frac{m(m+1)}{2}$ variables in $F\left(m\right)$. Notice that the ordering of linear and quadratic terms in $M(n,m)$ has a feature that the quadratic terms $s_i{s}_j$ with $j<i$ occur in $M(n,m)$ only after the term $s_i$ occurs. This feature facilitates the calculation of $Q_n\left(\mathbf{s}\right)$ term by term as in the Berlekamp–Massey algorithm.

We first give a toy example to illustrate the above linear equations. Let $n=9$ and $m=3$. Then we have

$$\begin{array}{cc}\hfill M(n,m)& =\left({\mathbf{1}}_6^T\right|B_0(9,3)\left|B_1(9,3)\right|B_2(9,3))\hfill \\ & =\left(\begin{array}{ccccccc}1\hfill & s_0\hfill & s_1\hfill & s_0{s}_1\hfill & s_2\hfill & s_1{s}_2\hfill & s_0{s}_2\hfill \\ 1\hfill & s_1\hfill & s_2\hfill & s_1{s}_2\hfill & s_3\hfill & s_2{s}_3\hfill & s_1{s}_3\hfill \\ 1\hfill & s_2\hfill & s_3\hfill & s_2{s}_3\hfill & s_4\hfill & s_3{s}_4\hfill & s_2{s}_4\hfill \\ 1\hfill & s_3\hfill & s_4\hfill & s_3{s}_4\hfill & s_5\hfill & s_4{s}_5\hfill & s_3{s}_5\hfill \\ 1\hfill & s_4\hfill & s_5\hfill & s_4{s}_5\hfill & s_6\hfill & s_5{s}_6\hfill & s_4{s}_6\hfill \\ 1\hfill & s_5\hfill & s_6\hfill & s_5{s}_6\hfill & s_7\hfill & s_6{s}_7\hfill & s_5{s}_7\hfill \end{array}\right),\hfill \end{array}$$

and

$$F\left(3\right)={(a,a_0,a_1,a_{0,1},a_2,a_{1,2},a_{0,2})}^T,E(9,3)={(s_3,s_4,s_5,s_6,s_7,s_8)}^T.$$

From the relation $M(9,3)F\left(3\right)=E(9,3)$, we obtain 6 equations with 7 variables in $F\left(3\right)$.

It is straightforward to see that the system is solvable if and only if

$$rank\left(M\right(n,m\left)\right)=rank\left(M\right(n,m)\mid E(n,m\left)\right).$$

Chan and Games in [43] had the following observation.

Theorem 3.

If an m-stage quadratic FSR can generate ${\mathbf{s}}_{n-1}$ but not ${\mathbf{s}}_n$, then there is no m-stage quadratic FSR that can generate ${\mathbf{s}}_n$ if and only if

$$rank\left(M\right(n,m\left)\right)=rank\left(M\right(n-1,m\left)\right).$$

By this theorem, for each step, when $s_0{s}_1\dots s_{n-2}$ has quadratic complexity m, if $rank\left(M\right(n,m\left)\right)\ne rank\left(M\right(n-1,m\left)\right),$ then $s_0{s}_1\dots s_{n-2}{s}_{n-1}$ for any $s_{n-1}$ also has the same quadratic complexity m. Based on such an observation, they proposed a term-by-term algorithm, similarly to the Berlekamp–Massey algorithm, to calculate the quadratic complexity of a sequence ${\mathbf{s}}_n$ [23]. Their algorithm strongly depends on the Gaussian elimination for the computation of $rank\left(M\right(n,m\left)\right)$ for each new term. The special structure of the matrix $M(n,m)$ was not well taken into consideration in their algorithm, which did not reveal the precise increment of the quadratic complexity of ${\mathbf{s}}_n$. By looking into certain structure of the matrix $M(n,m)$, Youssef and Gong [44] showed that if the quadratic complexity of the first n terms of a sequence $\mathbf{s}$, is larger than $n/2$, then the first $n+1$ terms of $\mathbf{s}$ has the same quadratic complexity. Rizomiliotis, Kolokotronis and Kalouptsidis in [45] observed the following nesting structure of the matrix $M(n,m)$:

$$\begin{array}{cc}\hfill M(n,m)& =\left(\begin{array}{c}M(n-1,m)\hfill \\ R_{n-m-1}(n,m)\hfill \end{array}\right)=\left(M(n-1,m-1)\mid B_{m-1}(n,m)\right)\hfill \\ & =\left(\begin{array}{c}{R}_0(n,m)\hfill \\ M^{\prime }(n,m)\hfill \end{array}\right),\hfill \end{array}$$

where $R_{n-m-1}(n,m)$ is the last row in $M(n,m)$, $R_0(n,m)$ is the starting row of $M(n,m)$, and $M^{\prime }(n,m)$ contains all the columns of $M(n,m+1)$ with indices of the form with indices of the form $j=\frac{b(b+1)}{2}+k$, with $0\le k\le b<m$, including the starting all one column ${\mathbf{1}}_{n-(m+1)}^T$ in $M(n,m+1)$. This nesting structure played an important role in the their derivation of the following results.

Theorem 4.

Suppose $Q_{n-1}\left(\mathbf{s}\right)<Q_n\left(\mathbf{s}\right)$. Then, $Q_n\left(\mathbf{s}\right)$ is the smallest integer m such that

$$rank\left(M\right(n,m\left)\right)\ne rank\left(M\right(n-1,m\left)\right).$$

Theorems 3 and 4 laid the foundation for an algorithmic method to calculate the quadratic complexity of a sequence. More specifically, for each new term, Theorem 3 determines when the quadratic complexity will increase; and Theorem 4 characterizes how large the increment is. Combining different cases for each new term, Figure 2 provides a preliminary algorithm to recursively assess the quadratic complexity of a sequence $\mathbf{s}$. It can be seen from Figure 2 that the assessment heavily depends on the calculation of ranks of involved matrices, which becomes slower as n and m grow.

With a detailed analysis of the nesting structure of $M(n,m)$, the authors in [45] proposed a more efficient algorithm (as in [45], Figure 3) to calculate the quadratic complexity profile of ${\mathbf{s}}_n$. In addition, when $n<\frac{m(m+3)}{2}+1$, the system $M(n,m)F\left(m\right)=E(n,m)$ is under-determined; and when $n\ge \frac{m(m+3)}{2}+1$, the necessary and sufficient condition that a unique quadratic feedback function generating the sequence ${\mathbf{s}}_n$ can be given [45].

Theorem 5.

The quadratic feedback function of an m-stage FSR that generates the sequence ${\mathbf{s}}_n$ is unique if and only if

$$rank\left(M(n,m)\right)=\frac{m(m+1)}{2}+1.$$

Otherwise, there are $2^{1+\frac{m(m+1)}{2}-rank\left(M(n,m)\right)}$ such functions.

This theorem illustrates that a binary sequence $\mathbf{s}$ with small quadratic complexity m should not be used for cryptographic applications. Otherwise, when $O\left(\frac{m(m+3)}{2}\right)$ consecutive components $s_i$’s in $\mathbf{s}$ are known, the quadratic feedback function could be (uniquely) determined, thereby producing the whole sequence and violating the requirement of unpredictability for sequences used in cryptography.

In the previous section, we saw a good theoretical understanding of the statistical behavior of linear complexity and linear complexity profile for random sequences. However, to the best of my knowledge, there is no published theoretical result on the statistical behavior for quadratic complexity and the quadratic complexity profile of random sequences ${\mathbf{s}}_n$ and n-periodic sequences ${\mathbf{s}}_n^{\infty }$, except for the following two conjectures by Youssef and Gong [44] strongly indicated by numerical results.

Conjecture 1.

Let $N_n\left(q_c\right)$ be the number of binary sequences ${\mathbf{s}}_n$ with quadratic complexity $q_c=Q\left(\mathbf{s}\right)>n/2$. Then $N_n\left(q_c\right)=N_{n+i}(q_c+i)$ for any $i\ge 1$, indicating that $N_n\left(q_c\right)$ is a function of $n-q_c$.

Conjecture 2.

For moderately large n, the expected value of the quadratic complexity of a random binary sequence of length n is given by

$$E\left[Q_n\right]\approx \sqrt{2n}.$$

5. Maximum-Order Complexity

As an additional figure of merit for randomness testing, Jansen and Boekee in 1989 proposed the notion of maximum-order complexity, also later known as nonlinear complexity, of sequences [46]. We adopt the term maximum-order complexity in this survey for better distinction from the notion of quadratic complexity.

Definition 4.

The maximum-order complexity of a sequence $\mathbf{s}=s_0{s}_1{s}_2\dots$, denoted by $M\left(\mathbf{s}\right)$, is the length of the shortest FSRs that can generate the sequence $\mathbf{s}$. Similarly, the maximum-order complexity profile of $\mathbf{s}$ is a sequence of $M_0\left(\mathbf{s}\right),M_1\left(\mathbf{s}\right),M_2\left(\mathbf{s}\right),\dots ,$ where $M_n\left(\mathbf{s}\right)$ for each $n\ge 0$ is the shortest FSRs that can generate the first n terms of $\mathbf{s}$.

As pointed out in ref. [46], the significance of the maximum-order complexity is that it tells exactly how many terms of $\mathbf{s}$ have to be observed at least in order to be able to generate the entire sequence by means of an FSR with length $M\left(\mathbf{s}\right)$. Therefore, it has been considered as an important measure to judge the randomness of sequences. Below we recall some basic properties of maximum-order complexity of sequences [46,47].

Lemma 1.

Let $\mathbf{s}=s_0{s}_1{s}_2\cdots$ be a sequence over ${\mathbb{F}}_q$.

(i) Let l be the length of the longest subsequence of $\mathbf{s}$ that occurs at least twice with different successors. Then the sequence $\mathbf{s}$ has maximum-order complexity $M\left(\mathbf{s}\right)=l+1$;

(ii) The maximum-order complexity of any n-length sequence is at most $n-1$. Moreover, the equality holds if and only if ${\mathbf{s}}_n$ has the form $(\alpha ,\cdots ,\alpha ,\beta )$ with $\alpha \ne \beta$ in ${\mathbb{F}}_q$.

Lemma 2.

Let $\mathbf{s}={\mathbf{s}}_n^{\infty }$ be a sequence of period n over ${\mathbb{F}}_q$.

(i) The maximum-order complexity of $\mathbf{s}$ satisfies $\lceil {log}_q\left(n\right)\rceil \le M\left(\mathbf{s}\right)\le n-1$;

(ii) The reciprocal sequence ${\mathbf{s}}^{*}={(s_{n-1},\dots ,s_0)}^{\infty }$ has $M\left({\mathbf{s}}^{*}\right)=M\left(\mathbf{s}\right)$.

From Lemmas 1 and 2, the difference between nonlinear complexities of finite-length sequences and periodic sequences is apparent. One typical difference is that the maximum-order complexity of a periodic sequence remains unchanged under cyclic shift operations, while that of a finite-length sequence can change dramatically. For instance, for the sequence $0\dots 01$ of length n, while $M(0\dots {01}^{\infty })=M(0\dots 01)=n-1$, after a right cyclic shift, we have $M(10\dots 0^{\infty })=n-1$ but $M(10\dots 0)=1$.

Recall that for the case where the linear feedback function is unique for periodic sequences, and that for the quadratic feedback function is also unique when the matrix $M(n,m)$ with $n=\frac{m(m+3)}{2}+1$ is nonsingular, the situation for maximum-order complexity is significantly different.

Proposition 6.

Let ${\mathrm{\Phi }}_{\mathbf{s}}$ denote the class of feedback functions of the FSRs that can generate a periodic sequence $\mathbf{s}=s_n^{\infty }$ with maximum-order complexity m over ${\mathbb{F}}_q$. Then the number of functions in ${\mathrm{\Phi }}_{\mathbf{s}}$ is equal to $|{\mathrm{\Phi }}_{\mathbf{s}}|=q^{q^m-n}.$

By the above proposition, the class ${\mathrm{\Phi }}_{\mathbf{s}}$ generally contains more than one feedback function that can generate the periodic sequence, which is similar for non-periodic sequences. One can search for functions exhibiting certain properties, such as the function with the least number of terms. One of the methods that minimize the number of terms and their orders in the inclusive-or sum of products of variables or their complements is to use the disjunctive normal form (DNF) representation of the feedback function. For the binary case, the DNF of f is given by

$$f(x_0,x_1,\dots ,x_{m-1})=\sum _{b_0,\dots ,b_{m-1}\in {\mathbb{F}}_2}f(b_0,\dots ,b_{m-1})x_0^{b_0}\cdots x_{m-1}^{b_{m-1}},$$

where $x_i^{b_i}=x_i+b_i+1=1$ if and only if $x_i=b_i$ for $0\le i<m$. It is also interesting to note that a unique feedback function occurs for DeBruijn sequences of order m, which have m-tuples over ${\mathbb{F}}_q$ exactly once in one period $q^m$. For binary DeBruijn sequences of order m, Chan and Games in [23] showed their quadratic complexity are upper bounded by $2^m-1-\left(\genfrac{}{}{0pt}{}{m}{2}\right)$, which can be reached by those DeBruijn sequences derived from m-sequences by inserting 0 to the all-zero subsequence of length $m-1$ in m-sequences.

5.1. Computation and Statistical Behavior

In ref. [46] Jansen associated $M\left(\mathbf{s}\right)$ with the maximum depth of a direct acyclic word graph (DAWG) from $\mathbf{s}$. Below, we recall a toy example from [46] to generate a DAWG from a binary string, which helps readers better understand relevant notions.

Example 1.

The sequence $\mathbf{s}=110100$ has the following set of all subsequences

$$\begin{array}{cc}\hfill \mathrm{SUB}\left(\mathbf{s}\right)=\{& \lambda ,1,0,11,10,01,00,110,101,010,100,\hfill \\ & 1101,1010,0100,11010,10100,110100\},\hfill \end{array}$$

where λ represents the empty sequence. For the sequence $\mathbf{s}$, the endpoints are given as in

Table 1. Endpoints for $\mathbf{s}=110100$.

s		1	1	0	1	0	0
endpoints	0	1	2	3	4	5	6

.

For the sub-sequences of $\mathbf{s}$, their endpoints are given as below

$$\begin{array}{cccc}E\left(\lambda \right)\hfill & =\{0,1,2,3,\hfill & 4,5,6\}\hfill & \\ E\left(1\right)\hfill & =\{1,2,4\},\hfill & E\left(0\right)\hfill & =\{3,5,6\},\hfill \\ E\left(11\right)\hfill & =\left\{2\right\},\hfill & E\left(10\right)\hfill & =\{3,5\},\hfill \\ E\left(01\right)\hfill & =\left\{4\right\},\hfill & E\left(00\right)\hfill & =\left\{6\right\},\hfill \\ E\left(110\right)\hfill & =\left\{3\right\},\hfill & E\left(101\right)\hfill & =\left\{4\right\},E\left(010\right)=\left\{5\right\},E\left(100\right)=\left\{6\right\},\hfill \\ E\left(1101\right)\hfill & =\left\{4\right\},\hfill & E\left(1010\right)\hfill & =\left\{5\right\},E\left(0100\right)=\left\{6\right\},\hfill \\ E\left(11010\right)\hfill & =\left\{5\right\},\hfill & E\left(10100\right)\hfill & =\left\{6\right\},\hfill \\ E\left(110100\right)\hfill & =\left\{6\right\}.\hfill & \hfill \end{array}$$

Subsequences are considered equivalent if they have the same set of endpoints. For instance, the following are three equivalent classes with endpoints 4, 5 and 6, respectively:

$$\begin{array}{cc}& E_4:01,101,1101\hfill \\ & E_5:010,1010,11010,\hfill \\ & E_6:00,100,0100,10100,110100.\hfill \end{array}$$

Therefore, the total 17 subsequences in $\mathrm{SUB}\left(\mathbf{s}\right)$ are divided into 9 equivalence classes. It is customary to choose the shortest subsequence as the class representative. In this way, we have the following representatives:

$$EQ\left(\mathbf{s}\right)=\{\lambda ,1,0,11,10,01,00,110,010\}.$$

From the above discussion, we can build a DAWG as follows: each representative in $EQ\left(\mathbf{s}\right)$ is denoted by a node and λ is considered as the source node; there is a directed edge between one node $v_i$ to another node $v_j$ if and only if the equivalence class of $v_i$ contains a subsequence, which when extended with the edge symbol belongs to the equivalence class of $v_j$; the edges are divided into primary and secondary edges: an edge is primary if and only if it belongs to a primary path (the longest path from the source to the node) and a depth of a node is the length of the primary path to the node, where the length of a path is the number of edges along the path. Let $BN\left(\mathbf{s}\right)$ be a subset consisting of nodes with more than one outgoing primary edges in $EQ\left(\mathbf{s}\right)$ and define the maximum depth $d\left(\mathbf{s}\right)={max}_{v\in BN\left(\mathbf{s}\right)}d\left(v\right)$.

In this way, we obtain the DAWG of the sequence $\mathbf{s}=110100$ as in Figure 3, where primary edges are displayed in solid arrows. From the definition of the depth of a node, we have

$$\begin{array}{cc}& d\left(\lambda \right)=0,d\left(0\right)=d\left(1\right)=1,\hfill \\ & d\left(11\right)=d\left(10\right)=2,d\left(01\right)=4,d\left(00\right)=6,\hfill \\ & d\left(110\right)=3,d\left(010\right)=5.\hfill \end{array}$$

Since $BN\left(\mathbf{s}\right)=\{\lambda ,1,0,10\}$, we have $d\left(\mathbf{s}\right)=d\left(10\right)=2.$

Figure 3. Direct acyclic word graph of $\mathbf{s}=110100$ [21].

Figure 3. Direct acyclic word graph of $\mathbf{s}=110100$ [21].

With the notions illustrated in Example 1, Jansen in [21] established the following connection between the maximum-order complexity of a sequence $\mathbf{s}$ and the depth of DAWG derived from $\mathbf{s}$, and proposed to calculate the maximum-order complexity of $\mathbf{s}$ from its DAWG.

Proposition 7.

Given a sequence $\mathbf{s}$, the maximum-order complexity of $\mathbf{s}$ and the depth $d\left(\mathbf{s}\right)$ of its DAWG satisfy

$$M\left(\mathbf{s}\right)=\left\{\begin{array}{cc}0,\hfill & ifBN\left(\mathbf{s}\right)=\varnothing ,\hfill \\ d\left(\mathbf{s}\right)+1,\hfill & otherwise.\hfill \end{array}\right.$$

Blumer’s algorithm [48] was identified as an important tool to build a DAWG of a sequence $\mathbf{s}$, thereby calculating its maximum-order complexity profile in linear time and memory with regard to the sequence length. The method worked particularly well for periodic sequences. With this algorithm, Jansen exhausted all $2^l$ binary l-length sequences and l-periodic sequences as l ranges from 1 up to 24 ([21], Tables 3.1–3.4), which exhibited typical statistical behaviors of maximum-order complexity profiles of random sequences: the expected maximum-order complexity of a random sequence $\mathbf{s}$ of sufficiently large length n over ${\mathbb{F}}_q$ is given by

$$E\left(M_n\left(\mathbf{s}\right)\right)\approx 2{log}_q\left(n\right).$$

Following the successful approach in ref. [45], Rizomiliotis and Kalouptsidis [49] considered the calculation of the maximum-order complexity of a sequence $\mathbf{s}$ in a similar way. From the recursive equations $f(s_i,s_{i+1},\dots ,s_{i+m-1})=s_{i+m}$ for $0\le i<n-m$, one can obtain a similar system to linear equations

$$M(n,m)F\left(m\right)=E(n,m),$$

where the coefficient matrix $M(n,m)$ from all binary terms ${\prod }_{i=0}^{m-1}{x}_i^{j_i}$, where $(j_0,j_1,\dots ,j_{m-1})$ is any element in ${\mathbb{F}}_2^m$ in a special ordering according to the degree of the terms. For instance, when $n=10$ and $m=3$, the system of linear equations is given by

$$M(10,3)=\left(\begin{array}{cccccccc}1\hfill & s_0\hfill & s_1\hfill & s_2\hfill & s_0{s}_1\hfill & s_0{s}_2\hfill & s_1{s}_2\hfill & s_0{s}_1{s}_2\hfill \\ 1\hfill & s_1\hfill & s_2\hfill & s_3\hfill & s_1{s}_2\hfill & s_1{s}_3\hfill & s_2{s}_3\hfill & s_1{s}_2{s}_3\hfill \\ 1\hfill & s_2\hfill & s_3\hfill & s_4\hfill & s_2{s}_3\hfill & s_2{s}_4\hfill & s_3{s}_4\hfill & s_2{s}_3{s}_4\hfill \\ 1\hfill & s_3\hfill & s_4\hfill & s_5\hfill & s_3{s}_4\hfill & s_3{s}_5\hfill & s_4{s}_5\hfill & s_3{s}_4{s}_5\hfill \\ 1\hfill & s_4\hfill & s_5\hfill & s_6\hfill & s_4{s}_5\hfill & s_4{s}_6\hfill & s_5{s}_6\hfill & s_4{s}_5{s}_6\hfill \\ 1\hfill & s_5\hfill & s_6\hfill & s_7\hfill & s_5{s}_6\hfill & s_5{s}_7\hfill & s_6{s}_7\hfill & s_5{s}_6{s}_7\hfill \\ 1\hfill & s_6\hfill & s_7\hfill & s_8\hfill & s_6{s}_7\hfill & s_6{s}_8\hfill & s_7{s}_8\hfill & s_6{s}_7{s}_8\hfill \end{array}\right)$$

with

$$\begin{array}{cc}& F\left(3\right)={(a,a_0,a_1,a_3,a_0{a}_1,a_0{a}_2,a_1{a}_2,a_0{a}_1{a}_2)}^T,\hfill \\ & E(10,3)={(s_3,s_4,s_5,s_6,s_7,s_8,s_9)}^T.\hfill \end{array}$$

In ref. [49], the authors investigated the properties of the m-tuples $T_j(n,m)=(s_j,s_{j+1},\dots ,s_{j+m-1})$ as j runs through the indices $0,1,\dots ,n-m$ and proposed a term-by-term algorithm to compute the maximum-order complexity and output a feedback function for a given sequence ${\mathbf{s}}_n$. They also pointed out that the dominant multiplication complexity in their proposed algorithm is in the order of $O\left(n\right)$.

Attempting the above approach by analyzing the structure of $M(n,m)$ is not satisfactory enough. Later, in ref. [50], the authors made more observations that further improved the performance of calculating maximum-order complexity of sequences.

Proposition 8.

For a binary sequence $\mathbf{s}$, suppose $M_{n-1}\left(\mathbf{s}\right)=m$ and the minimal FSR of $s_0{s}_1\dots s_{n-2}$ does not generate $s_0{s}_1\dots s_{n-2}{s}_{n-1}$. Then $M_n\left(\mathbf{s}\right)=m$ if and only if the subsequence $s_{n-m-1}{s}_{n-m}\dots s_{n-2}$ has not appeared within ${\mathbf{s}}_{n-1}$.

The above observation is a natural extension of the property of maximum-order complexity in Lemma 1 (i). Instead, the following observation characterized the jump of maximum-order complexity profile at each term.

Proposition 9.

For a binary sequence $\mathbf{s}$, suppose $M_{n-1}\left(\mathbf{s}\right)=m<M_n\left(\mathbf{s}\right)$. Let $i\le n-m-1$ be the least integer such that $s_j\dots s_{j+m-1}=s_i\dots s_{i+m-1}$ for certain $0\le j<i$. Then $M_n\left(\mathbf{s}\right)=M_{n-1}\left(\mathbf{s}\right)+(n-m-i)=n-i.$ Moreover, if $M_n\left(\mathbf{s}\right)=m+k$ for $k\ge 1$, then the sequence ${\mathbf{s}}_n\left|\right|s_n\cdots s_{n+k-1}$ by arbitrary extension $s_n\dots s_{n+k-1}$ has the same maximum-order complexity $m+k$.

In addition, they observed that the maximum-order complexity profile of a sequence has a close connection to its eigenvalue profile. To be more concrete, the eigenwords in a sequence $s_0{s}_1\dots s_{r-1}$ are those subsequences of $s_0{s}_1\dots s_{r-1}$ that are not contained in any proper subsequence $s_0\dots s_{t-1}$ of $s_0{s}_1\dots s_{r-1}$. They showed the following interesting connection.

Theorem 6.

For a binary sequence $\mathbf{s}$, suppose $M_{n-1}\left(\mathbf{s}\right)=m$ and the minimal FSR of ${\mathbf{s}}_{n-1}$ does not generate ${\mathbf{s}}_n$. Then,

$$M_n\left(\mathbf{s}\right)=max\{M_{n-1}\left(\mathbf{s}\right),n-\mathrm{Eigenvalue}\left({\mathbf{s}}_{n-1}\right),\}$$

where $\mathrm{Eigenvalue}\left({\mathbf{s}}_{n-1}\right)$ is the number of eigenwords in the sequence ${\mathbf{s}}_{n-1}$.

From the observations on the update of certain feedback function when the minimal FSR of ${\mathbf{s}}_{n-1}$ does not generate ${\mathbf{s}}_n$, they proposed the following procedure to generate a minimal feedback function and maximum-order complexity of a sequence $\mathbf{s}$. Suppose $M_{n-1}\left(\mathbf{s}\right)=m$ and the minimal feedback function of ${\mathbf{s}}_{n-1}$ is $h_{n-1}(x_0,\cdots ,x_{m-1})$. Then,

• if $s_{n-1}=h_{n-1}(s_{n-m-1},\dots ,s_{n-2})$, then ${\mathbf{s}}_n$ and ${\mathbf{s}}_{n-1}$ share the minimal feedback function $h_{n-1}$ and the same maximum-order complexity m
• if $s_{n-1}\ne h_{n-1}(s_{n-m-1},\dots ,s_{n-2})$ and $M_n\left(\mathbf{s}\right)=M_{n-1}\left(\mathbf{s}\right)$, then update $h_{n-1}$ as

  $$h_n(x_0,\dots ,x_{m-1})=h_{n-1}(x_0,\dots ,x_{m-1})+\prod _{i=n-m-1}^{n-2}(x_i+s_i+1)$$
• if $s_{n-1}\ne h_{n-1}(s_{n-m-1},\dots ,s_{n-2})$ and $M_n\left(\mathbf{s}\right)=m+k$, then

  $$h_n(x_0,\dots ,x_{m+k-1})=h_{n-1}(x_0,\dots ,x_{m+k-1})+\prod _{i=n-m-k-1}^{n-2}(x_i+s_i+1)$$

Consequently, they proposed an efficient algorithm for maximum-order complexity, which works very similarly to the Berlekamp–Massey algorithm. For ease of comparison with the Berlekamp–Massey algorithm, we recall it in Algorithm 1. The computational complexity of Algorithm 1 in the worse case is $O\left(n^3\right)$, while in the average case is $O\left(n^2{log}_2\left(n\right)\right)$ since the the expected maximum-order complexity $E\left[M_n\right]\approx 2{log}_2\left(n\right)$. While it has the similar complexity as the DAWG method [21], its recursive nature is an important advantage since it eliminates the need to know the entire sequence in advance. This resembles the well-known Berlekamp–Massey algorithm in the linear case: if a discrepancy occurs at certain step, then a well-determined corrective function is added to the current minimal feedback function of ${\mathbf{s}}_{n-1}$ to provide an updated minimal feedback of ${\mathbf{s}}_n$. In addition, the update of maximum-order complexity $M_n\left(\mathbf{s}\right)=max\{M_{n-1}\left(\mathbf{s}\right),n-\mathrm{Eigenvalue}\left({\mathbf{s}}_{n-1}\right)\}$ at each step is similar to $L_n\left(\mathbf{s}\right)=max\{L_{n-1}\left(\mathbf{s}\right),n-L_{n-1}\left(\mathbf{s}\right)\}$ for linear complexity of the sequence $\mathbf{s}$ in the recursive procedure.   

Algorithm 1: Generation of minimal polynomial for $\mathbf{s}$.

5.2. Approximate Statistical Behavior

Conducting a rigorous theoretical analysis of the behavior of maximum-order complexity profiles, as was done for linear complexity, appeared intractable. On the other hand, maximum-order complexity had a lot of similarities as linear complexity. In order to facilitate the randomness test with maximum-order complexity, Erdman and Murphy proposed a method to approximate the distribution of the maximum-order complexity [51]. Inspired by the property of maximum-order complexity in Lemmas 1 and 2, they investigated a function that approximates the function $P(m,n)$: the probability that the first nm-tuples are all different in a sequence.

Proposition 10.

Let $R(m,n-1)$ be the probability that the n-th m-tuple is unique given that the previous $(n-1)$ m-tuples were unique. Then,

$$P(m,n)=\prod _{i=1}^{n}R(m,i)\approx \prod _{i=1}^n\left(1-\frac{i+1}{2^{m+1}}\right)=p(m,n).$$

Simulations on random sequences for m from 4 to 24 ([51], Table 2) indicated that the above approximation was accurate, particularly when $m\ge 17$.

Recall that a purely periodic sequence has maximum-order complexity m if the first nm-tuples are unique but at least one of the first n$(m-1)$-tuples is repeated. Thus, for calculating a periodic sequence $\mathbf{s}={\mathbf{s}}_n^{\infty }$, it suffices to only look at the first $n+m-1$ bits to see if the nm-tuples are unique and the first $n+m-2$ bits to see if the n$(m-1)$-tuples are not unique. Denote by $Q(m,n)$ the probability that the first nm-tuples are unique while the n$(m-1)$-tuples are not. This probability function can be well approximated by $q(m,n)$, which is given by

$$q(m,n)=\left\{\begin{array}{cc}p(m,n)-p(m-1,n),\hfill & \mathrm{if}n\le 2^{m-1},\hfill \\ p(m,n)\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

Based on this approximation (of which the accuracy was shown in ([51], Table 3)), the expected maximum-order complexity was approximated as follows:

Theorem 7.

Let $M_n$ be the maximum-order complexity of a random periodic binary sequence ${\mathbf{s}}_n^{\infty }$. Then,

$$\begin{array}{cc}\hfill E\left[M_n\right]& =\sum _{m={log}_2\left(n\right)}^{n-1}mQ(m,n)=(n-1)-\sum _{m={log}_2\left(n\right)}^{n-2}P(m,n)\hfill \\ \hfill & \approx (n-1)-\sum _{m={log}_2\left(n\right)}^{n-2}p(m,n)\hfill \\ \hfill & =(n-1)-\sum _{m={log}_2\left(n\right)}^{n-2}\prod _{i=1}^n\left(1-\frac{i+1}{2^{m+1}}\right).\hfill \end{array}$$

Similarly, for random binary sequences of length n, the expected maximum-order complexity was approximated below.

Theorem 8.

Let $N(m,n)$ be the number of binary sequences of length n with maximum-order complexity m. Then, it can be approximated as

$$N(m,n)\approx 2^{n}q(m,n-m+1),$$

and the expected maximum-order complexity ${\widehat{M}}_n$ of random binary sequence of length n is given by

$$\begin{array}{cc}\hfill E\left[{\widehat{M}}_n\right]& =\sum _{m=0}^{n-1}m\frac{N(m,n)}{{\sum }_{i=0}^{n-1}N(i,n)}\hfill \\ & \approx \sum _{m=0}^{n-1}m\frac{2^{n}q(m,n-m+1)}{{\sum }_{i=0}^{n-1}{2}^{n}q(i,n-i+1)}\hfill \\ & \approx 2{log}_2\left(n\right)\left(forsufficientlylargen\right).\hfill \end{array}$$

5.3. Sequences with High Maximum-Order Complexity

Different complexity measures were proposed in the literature to evaluate the randomness of sequences. A sequence with low complexity, including the linear, quadratic and maximum-order complexity, allows for short FSRs to generate the whole period of the sequence. That is to say, all remaining unknown terms in this sequence can be efficiently uncovered when the feedback function and the initial state of the short FSRs are determined. It is clear that this kind of sequences should be avoided for any cryptographic applications. On the other hand, the relation between high complexity of a sequence and good randomness of a sequence is not yet well understood.

For the aforementioned complexity measures, the sequences of the form $(0,\dots ,0,1)$ have the largest complexity, but have clearly poor randomness. According to the exhaustive search results on maximum-order complexity in Tables 1–3 in [21], while sequences $(0,\dots ,0,1)$ are the only instances of n-length sequences that have the highest possible complexity $n-1$, there are multiple n-periodic binary sequences having the highest maximum-order complexity $n-1$.

Researchers have been interested in the study of sequences with high maximum-order complexity [52,53], particularly on sequences having highest possible maximum-order complexity [54,55]. For the latter case, Rizomiliotis [49] in 2005 proposed the following necessary and sufficient condition for an n-periodic binary sequence to have maximum-order complexity the same as its linear complexity.

Proposition 11.

For a periodic binary sequence $\mathbf{s}={\mathbf{s}}_n^{\infty }$, let ${\mathbf{s}}_n\left(x\right)=s_0+s_{1}x+\cdots +s_{n-1}{x}^{n-1}$ be the polynomial representation of ${\mathbf{s}}_n$, and let $h\left(x\right)=gcd(x^n+1,{\mathbf{s}}_n\left(x\right))$, $c\left(x\right)={\mathbf{s}}_n\left(x\right)/h\left(x\right)$ and $f\left(x\right)=x^n+1/gcd(x^n+1,{\mathbf{s}}_n\left(x\right))$. Then,

$$M\left(\mathbf{s}\right)=min\{n-1,L(\mathbf{s}\left)\right\}$$

(10)

if and only if there exists integers $0\le p_1<p_2\le n-1$ satisfying

$$f\left(x\right)|1+(x^{p_1}+x^{p_2}\left(x\right))c\left(x\right)$$

when $LC\left(\mathbf{s}\right)\le n-1$.

Based on the above condition, different families of n-periodic binary sequences that have the same linear complexity and maximum-order complexity were proposed in ref. [49]. Moreover, an algorithm based on Lagrange interpolation and an algorithm based on the relative shift of the component sequences were proposed to generate binary sequences with highest possible maximum-order complexity. These two ideas were further developed for constructing such periodic sequences with period of the form $2^m-1$ [54]. Roughly 10 years later, n-periodic sequences with highest maximum-order complexity were revisited in ref. [55], which provided a complete picture of sequences with maximum-order complexity. The authors of ref. [55] gave the necessary and sufficient condition for n-periodic sequences over any alphabet to have maximum-order complexity $n-1$.

Theorem 9.

Let $\mathbf{s}={\mathbf{s}}_n^{\infty }$ be an n-periodic sequence over any field $\mathbb{F}$. Then $M\left(\mathbf{s}\right)=n-1$ if and only if there exists an integer p with $1\le p<n$ such that $s_i=s_{i+p(modn)}$ for $0\le i<n-2$ and $s_i\ne s_{i+p(modn)}$ for $i=n-2,n-1$. Furthermore, such a sequence can, up to shift equivalence, be represented as one of the following forms

(1) ${\mathbf{s}}_n=\left({\alpha }^{n-1}\beta \right)=(\stackrel{n-1}{\overbrace{\alpha ,\cdots ,\alpha }},\beta )$ where $\alpha \ne \beta \in \mathbb{F}$;

(2) ${\mathbf{s}}_n={\mathbf{s}}_{r_0}={\left({\mathbf{s}}_{r_1}\right)}^{m_1}{\mathbf{s}}_{r_2}$ for certain integer $r_1\in {\mathbb{Z}}_n^{*}$ with

$${\mathbf{s}}_{r_{i-1}}={\left({\mathbf{s}}_{r_i}\right)}^{m_i}{\mathbf{s}}_{r_{i+1}},i=1,2,\cdots ,k,$$

and

$${\mathbf{s}}_{r_k}=\left({\left(\alpha \right)}^{r_k-1}\beta \right),{\mathbf{s}}_{r_{k+1}}=\left(\alpha \right),$$

where the integers $m_i,r_{i+1}$ for $i=1,2,\cdots ,k$ are derived from $r_{i+1}=$$r_{i-1}-m_i{r}_i$ with $r_1>r_2>\cdots >r_{k+1}=1$,

With the full characterization in Theorem 9, the distribution of random n-periodic binary sequences having maximum-order complexity $n-1$ can be derived as follows.

Proposition 12.

The probability that a randomly generated sequence $\mathbf{s}={\mathbf{s}}_n^{\infty }$ has the highest $M\left(\mathbf{s}\right)=n-1$ is given by

$$P_{n-1}=\mathrm{Prob}(M\left(\mathbf{s}\right)=n-1)=\frac{q(q-1)n\phi \left(n\right)}{2{\sum }_{d|n}\mu \left(d\right)q^{n/d}},$$

where $\phi (·)$ is the Euler’s totient function and $\mu (·)$ is the Möbius function given by $\mu \left(n\right)=$${\sum }_{k\in {\mathbb{Z}}_n^{*}}{e}^{2\pi ik/n}$. In particular, when $q=2$, the probability

$$P_{n-1}=\frac{\phi \left(n\right)}{{\sum }_{d\mid n}\mu \left(d\right)2^{\frac{n}{d}}}.$$

Interestingly, the sequences $\mathbf{s}$ characterized in Theorem 9 exhibit a strong recursive structure, which can be derived by applying the Euclidean algorithm on n and the integer p, a smaller period of a subsequence of ${\mathbf{s}}_n$. This strong recursive structure, on the other hand, implies that $\mathbf{s}$ is far from being random. As discussed in ref. [55], the balancedness, stability and scalability of such sequences are not good, indicating that they should be avoided for cryptographic applications. Very recently, binary sequences with periodic n were further studied in ref. [56], where the authors further investigated the structure of ${\mathbf{s}}_n^{\infty }$ and proposed an algorithmic method to determine all n-periodic binary sequences with maximum-order complexity $\ge n/2$.

In addition, Liang et al. recently investigated the structure of n-length binary sequences with high maximum-order complexity $\ge n/2$ and proposed an algorithm that can completely generate all those binary sequences [53]. Based on the completeness, they managed to provide an explicit expression of the number of n-length binary sequences with any maximum-order complexity between $n/2$ and n.

Proposition 13.

The number of n-length binary sequences with maximum-order complexity m with $n/2\le m\le n-1$ is given by

$$N(m,n)=\sum _{d=1}^{n-m}(n-m-d+2)2^{n-m-d-1}N(m,m+d,d)$$

where

$$N(m,m+d,d)=2^{n-m}-\sum _{t=1}^r{(-1)}^{t-1}\sum _{1\le j_1<\cdots <j_t}{2}^{\frac{n-m}{p_1^{j_1}\cdots p_t^{j_t}}}$$

when $n-m$ is factorized as $n-m=p_1^{j_1}\cdots p_r^{j_r}$.

6. Relations between Complexity Measures

Besides the complexity measures in the context of FSRs in previous sections, some other measures have been discussed by researchers, such as Lempel–Ziv complexity [57], 2-adic complexity for FSRs with carry operation [22], k-error complexity, expansion complexity [58] and correlation measure [59,60]. This section will briefly review the relations among these measures. Below we start with the relation between the complexity measures in the previous sections, and we will be mainly focusing on extreme cases.

6.1. Relations between FSR-Based Complexities

From their definitions, for a sequence $\mathbf{s}$, it is easily seen that

$$M_n\left(\mathbf{s}\right)\le Q_n\left(\mathbf{s}\right)\le L_n\left(\mathbf{s}\right)\le n.$$

We know that the special sequence of the form ${\mathbf{s}}_n=\alpha \dots \alpha \beta$, where $\alpha \ne \beta$, has the largest linear complexity n, quadratic and maximum-order complexity $n-1$. As for n-periodic sequences $\mathbf{s}={\mathbf{s}}_n^{\infty }$ over ${\mathbb{F}}_q$, the largest linear complexity is also n, which can be seen from the expression $L\left(\mathbf{s}\right)=n-deg(gcd(x^n-1,s_n\left(x\right)))$, as recalled in Proposition 5. This can be used to characterize the periodic sequences with largest linear complexity. Assume $n=p^{v}w$ with $gcd(p,w)=1$, where p is the characteristic of ${\mathbb{F}}_q$. Let $C_1=\left\{0\right\},C_2,\dots ,C_h$ be the cyclotomic cosets modulo w relative to the power q. Let $\beta$ be a primitive n-th root of unity in an extension of ${\mathbb{F}}_q$. Then, we have the following factorization of $x^n-1$ over ${\mathbb{F}}_q$:

$$x^n-1=\left(\prod _{1\le i\le h}{f}_j\left(x\right)\right)={\left(\prod _{1\le i\le h}\prod _{j\in C_i}(x-{\beta }^i)\right)}^{p^u},$$

which indicates that an n-periodic sequences over ${\mathbb{F}}_q$ has the largest linear complexity n if and only if

$$gcd(s_n\left(x\right),f_j)=1\mathrm{for}j=1,2,\dots ,h.$$

Niederreiter, in ref. [61], proved the existence of n-periodic sequences with the largest linear complexity n and large k-error linear complexity, which is defined as

$$L_k\left({\mathbf{s}}_n^{\infty }\right)=min\left\{L\left({\mathbf{t}}_n^{\infty }\right)\right|\mathrm{wt}({\mathbf{s}}_n-{\mathbf{t}}_n)\le k\}.$$

This result was obtained by finding integers $n=p^{v}w$ satisfying a condition, which was derived from the following observation [61]: let $l={min}_{2\le i\le h}\left|C_i\right|$ and suppose k is an integer such that ${\sum }_{j=0}^k\left(\genfrac{}{}{0pt}{}{n}{j}\right){(q-1)}^j<q^l$, then there exists an n-periodic sequence $\mathbf{s}$ satisfies

$$L\left(\mathbf{s}\right)=n\mathrm{and}{L}_k\left(\mathbf{s}\right)\ge n-p^v.$$

As shown in the examples in ref. [61], there are infinitely many primes n allowing for the existence of binary n-periodic sequences of maximum possible linear complexity n.

Finding n-periodic sequences with the largest maximum-order complexity seems more challenging, especially when k-error complexity is also considered. As recalled in Section 5, Sun et al. [55] revealed n-periodic sequences with the largest maximum-order complexity $n-1$, which have surprisingly strong recursive structure. Besides this, little results about k-error maximum-order complexity and quadratic complexity have been reported. Here, we propose two open problems for interested readers.

Problem 2.

Characterize all the n-periodic sequences over ${\mathbb{F}}_q$ with the largest quadratic complexity $n-1$.

Problem 3.

Characterize certain lower bound on the k-error maximum-order complexity of n-periodic sequences with maximum-order complexity $n-1$.

Another extreme case for sequences is that they have the least possible complexity values. For finite-length sequences, we know that the linear, quadratic and maximum-order complexity can be as small as zero, which do not appear to be interesting to explore. When $\mathbf{s}$ is a periodic sequence over ${\mathbb{F}}_q$, we know that m-sequences of length $n=q^m-1$ have the least complexities $M\left(\mathbf{s}\right)=Q\left(\mathbf{s}\right)=L\left(\mathbf{s}\right)=m$ and DeBruijn sequences of length $n=q^m$ have the least maximum-order complexity $M\left(\mathbf{s}\right)=m.$ In addition to the aforementioned observations, readers may wonder what else we know about their relations so far?

Due to the limited understanding of DeBruijn sequences, there have been only partial results for the above problem. It was well known [62] that the linear complexity of binary DeBruijn sequences of order m is between $2^{m-1}+m$ and $2^m-1$, where both the lower and upper bound are attainable. However, there exists no binary DeBruijn sequences with linear complexity $2^{m-1}+m+1$ [63]. Based on the evidence of existing results, Etzion, in his survey, made the following conjecture:

Conjecture 3.

For any integer $2^{m-1}+m+2\le d\le 2^m-1$, there exists a binary DeBruijn sequence with minimal polynomial ${(x+1)}^d$.

There is a close connection between m-sequence over ${\mathbb{F}}_q$ of order m and DeBruijn sequences of order m. There have been also some works on the linear complexity of modified DeBruijn sequences, which were obtained by removing one zero from the longest run of zeros in a DeBruijn sequence. Mayhew and Golomb [64] showed that the minimal polynomial of binary modified DeBruijn sequences of order m is a product of distinct irreducible polynomials with degrees not equal to 1 and dividing m. Further results on the restrictions of the degrees were developed in [65,66,67].

When considering the fact for a binary sequence $\mathbf{s}$ with low quadratic complexity m, any subsequence of length slightly larger than $\frac{(m+3)m}{2}+1$ can be sufficient to recover the whole sequence $\mathbf{s}$. However, the topic of quadratic complexity was significantly less explored. There has been little research progress on quadratic complexity, even though it was already studied in 1989. To the best of my knowledge, the only results about the quadratic complexity of DeBruijn sequences were reported by Chan and Games [23].

Proposition 14.

Given a binary DeBruijn sequence $\mathbf{s}$ of order $m\ge 3$, then

$$Q\left(\mathbf{s}\right)\le 2^m-\left(\genfrac{}{}{0pt}{}{m}{2}\right)-1.$$

In particular, this upper bound can be attained by the DeBruijn sequence derived from an m-sequence of order by including the all zero m-tuple.

In addition, numerical results for $m=3,4,5,6$ led to a conjecture in [23]: the quadratic complexity of binary DeBruijn sequences of order $m\ge 3$ is lower bounded by $m+2$. Three years later, this conjecture was later confirmed by Khachatrian in [68].

6.2. FSR-Based Complexities, Lempel–Ziv Complexity, Expansion Complexity and Autocorrelation

This subsection will briefly review recent works on the relations among the linear, maximum-order complexity and other significant metrics for assessing pseudo-random sequences.

6.2.1. 2-Adic Complexity

The 2-adic complexity introduced by Goresky and Klapper [22,69] is closely related to the length of a shortest feedback with carry shift register (FCSR) that generates the sequence. The theory of 2-adic complexity of periodic sequences has been well developed. Given a sequence $\mathbf{s}={\mathbf{s}}_n^{\infty }$ of period n, one has

$$\sum _{i=0}^{\infty }{s}_i{2}^i=-\frac{{\sum }_{i=0}^{n-1}{s}_i{2}^i}{2^n-1}=\frac{A}{q},$$

where $0\le A\le q,gcd(A,q)=1$ and

$$q=\frac{2^n-1}{gcd\left(2^n-1,{\sum }_{i=0}^{n-1}{s}_i{2}^i\right)}.$$

The 2-adic complexity of $\mathbf{s}$ is defined as $\mathrm{\Phi }\left(\mathbf{s}\right)={log}_2\left(q\right)$. In the aperiodic case, the n-th 2-adic complexity, denoted by ${\mathrm{\Phi }}_{2,n}\left(\mathbf{s}\right)$, is the binary logarithm of

$$min\left\{max\left\{\right|f|,|q\left|\right\}:f,q\in \mathbb{Z},q\mathrm{odd},q\sum _{i=0}^{n-1}{s}_i{2}^i\equiv f(mod{2}^n)\right\}.$$

There was very little work on exploring the relation between linear, quadratic and maximum-order complexities of a binary sequence and its 2-adic complexity. Until recently, it was shown [70] that the maximum-order complexity of a binary sequence $\mathbf{s}$ is upper bounded by its 2-adic complexity.

6.2.2. Lempel–Ziv Complexity

The Lempel–Ziv complexity of a sequence is one classical complexity measure based on pattern counting, introduced by Lempel and Ziv in 1976 [57] and later named after them. The parsing procedure in the calculation of Lempel–Ziv complexity laid the basis for the prominent Lempel–Ziv compression algorithms [71,72]. The Lempel–Ziv complexity reflects the compressibility of a sequence and thus has significant cryptographic interest.

The Lempel–Ziv complexity measures the rate at which new patterns emerge as we move along a given sequence. For a binary sequence ${\mathbf{s}}_n=s_0{s}_1\dots s_{n-1}$, we split up ${\mathbf{s}}_n$ into adjacent blocks. By definition, the first block consists of $s_0$. If $s_0\dots s_{m-1}$ is a union of blocks, or in other words if $s_{m-1}$ is the last bit in a block, then the next block $s_m\dots s_{m+k-1}$ is uniquely determined by two properties: (i) the sequence $s_m\dots s_{m+k-2}$ occurs as a subsequence in $s_1\dots s_{m+k-3}$; (ii) the sequence $s_m\dots s_{m+k-1}$ does not occur as a subsequence in $s_1\dots s_{m+k-2}$. The Lempel–Ziv complexity is then the number of blocks into which ${\mathbf{s}}_n$ is split up by this procedure.

Motivated by Niederreiter’s statement [31], Limniotis, Kolokotronis and Kalouptsidis explored the relation between the maximum-order complexity and Lempel–Ziv complexity of a sequence, which are both closely connected to the eigenvalue profile of the sequence. They pointed out that although the exhaustive history (which uniquely determines the Lempel–Ziv complexity) cannot fully estimate the maximum-order complexity profile and vise versa, there still exists a relationship between them in the sense that the eigenvalue profile of a sequence of given Lempel–Ziv complexity, which determines the maximum-order complexity profile, is restricted rather than arbitrary. They also established a lower bound on the compression ratio of sequences with a prescribed maximum-order complexity.

6.2.3. Expansion Complexity

In 2012, Diem introduced the notion of expansion complexity of sequences [24], in which he showed that the sequences over finite fields with optimal linear complexity proposed by Xing and Lam via function expansion [29] can be efficiently computed from a relatively short subsequence.

Let $\mathbf{s}=s_0{s}_1{s}_2\dots$ be a sequence over ${\mathbb{F}}_q$. For a positive integer n, the n th expansion complexity $E_n\left(\mathbf{s}\right)$ is 0 if $s_0=\cdots =s_{n-1}=0$ and otherwise the least total degree of a nonzero polynomial $h(x,y)={\sum }_{i,j}{h}_{ij}{x}^i{y}^j\in {\mathbb{F}}_q[x,y]$ with

$$h(x,G\left(x\right))\equiv 0\left(mod{x}^n\right),$$

where the total degree of $h(x,y)$ is given by

$$\begin{array}{cc}\hfill deg\left(h\right(x,y\left)\right)=& \underset{i,j\ge 0}{max}\left\{i+j\mid x^i{y}^j\right.\mathrm{is}\mathrm{a}\mathrm{monomial}\mathrm{of}\left.h(x,y),h_{ij}\ne 0\right\}.\hfill \end{array}$$

The expansion complexity of the sequence $\mathbf{s}$ is defined as

$$E\left(\mathbf{s}\right)=\underset{n\ge 1}{sup}{E}_n\left(\mathbf{s}\right).$$

It can be verified that $E_n\left(\mathbf{s}\right)\le E_{n+1}\left(\mathbf{s}\right)\le E_n\left(\mathbf{s}\right)+1$. In particular, if $h(x,y)$ is restricted to be irreducible, then the n-th irreducible expansion complexity and irreducible expansion complexity of $\mathbf{s}$ can be defined accordingly. The relations between the linear complexity, maximum-order complexity and expansion complexity were discussed recently in [58,73].

Proposition 15.

Let $\mathbf{s}$ be an ultimately periodic sequence with pre-period u, period n and linear complexity $L\left(\mathbf{s}\right)$. Then, the irreducible expansion complexity

$$E^{*}\left(\mathbf{s}\right)=\left\{\begin{array}{cc}L\left(\mathbf{s}\right)+1\hfill & ifu=0\hfill \\ L\left(\mathbf{s}\right)\hfill & ifu=1\hfill \\ L\left(\mathbf{s}\right)-1\hfill & ifu=2oru>2,s_{u-1}\ne s_{u+n-1}\hfill \end{array}\right.$$

and $E^{*}\left(\mathbf{s}\right)<L\left(\mathbf{s}\right)-1$ otherwise.

Proposition 16.

For any infinite sequence $\mathbf{s}$ over ${\mathbb{F}}_q$, if $M_n\left(\mathbf{s}\right)=n-k$ with $1\le k<\sqrt{2n}-2$ and $n>8$, then its n th expansion complexity $E_n\left(\mathbf{s}\right)$ is no more than $k+2$.

6.2.4. k-Order Correlation Measure

Let k be a positive integer. The n-th correlation measure of order k of a binary sequence $\mathbf{s}=s_0{s}_1{s}_2\dots$ is given by [74]

$$C_n(\mathbf{s},k)=\underset{u,\mathbf{d}}{max}\left|\sum _{i=0}^{u-1}{(-1)}^{s_{i+d_1}+s_{i+d_2}+\dots +s_{i+d_k}}\right|,$$

where the maximum is taken over all $\mathbf{d}=(d_1,d_2,\dots ,d_k)$ with non-negative integers $0\le d_1<d_2<\cdots <d_k$ and u such that $u+d_k<n$.

The relations between the linear complexity, maximum-order complexity and correlation measure of order k were explored in [59,60,74].

Proposition 17.

Given a binary sequence $\mathbf{s}=s_0{s}_1{s}_2\dots$, the n-th linear complexity and n-th correlation measure of $\mathbf{s}$ satisfy

$$L_n\left(\mathbf{s}\right)\ge n-\underset{1\le k\le L_n\left(\mathbf{s}\right)+1}{max}{C}_n(\mathbf{s},k),n\ge 1,$$

and the n-th maximum-order complexity and n-th correlation measure of $\mathbf{s}$ satisfy

$$M_n\left(\mathbf{s}\right)\ge N-2^{M_n\left(\mathbf{s}\right)+1}\underset{1\le k\le M_n\left(\mathbf{s}\right)+1}{max}{C}_n(\mathbf{s},k),n\ge 1.$$

The above bounds were recently improved in [60].

Proposition 18.

Given a binary sequence $\mathbf{s}=s_0{s}_1{s}_2\dots$, if for some integer t, the n-th linear complexity of $\mathbf{s}$ satisfies

$$2^{L_n\left(\mathbf{s}\right)}<\left(\genfrac{}{}{0pt}{}{\lfloor \frac{n}{2}\rfloor }{t}\right),$$

then for some k with $1<k\le 2t$, one has

$$C_n(\mathbf{s},k)\ge \lceil \frac{n}{2}\rceil .$$

In addition, if the n-th maximum-order complexity of $\mathbf{s}$ satisfies $M_n\left(\mathbf{s}\right)\le M$, then one has

$$C_n(\mathbf{s},2)\ge n-2^M+1.$$

7. Conclusions

This survey primarily focused on the complexity measures of sequences within the domain of feedback shift registers, which are efficiently computable and hold significant interest in cryptographic applications. Notable works on the computation, stochastic behavior and theoretical results of these complexities were examined to a certain technical extent. Several conjectures were revisited and new open problems were proposed. To offer a sounding overview of the research development on complexity measures, this survey also briefly reviewed the established relation between these complexities as well as their connection with other important metrics for pseudo-random sequences, including the well-known 2-adic complexity, Lempel–Ziv complexity, expansion complexity and k-order correlation measure. This survey indicates that although the study of complexity measures of randomness traces back to the 1960s, only linear complexity and maximum-order complexity are relatively well explored. Other complexity measures and their interrelations appear more intractable and require new tools, techniques and theoretical studies in future research.