Some Necessary Conditions for Feedback Functions of de Bruijn Sequences

For a positive integer n, an n-order binary de Bruijn sequence (dBS) is a binary periodic sequence of period 2ⁿ, where each n-tuple is contained just once [1]. Since dBSs have many desirable characteristics, including good randomness, long periods and large complexities, they have a very abroad applications in the field of information security, such as cryptography [2–5]. dBSs are easy to implement in hardware and they can be constructed by nonlinear feedback shift registers (NFSRs). Compared with the study of linear feedback shift registers (LFSRs), the theory of NFSRs has developed at a slower pace [3, 4].

So far, researchers have not given sufficient conditions for NFSRs to directly generate dBSs. In this case, a relatively weak problem is to find the necessary conditions for NFSRs to construct dBSs, which is considered to be important. Several necessary conditions for feedback functions (FFs) of NFSRs to produce dBSs have been given successively by some researchers.

Let f(x0,x1,⋯,xn−1)=x0+g(x1,⋯,xn−1)$f(x_0,x_1,\cdots,x_{n-1})=x_0+g(x_{1},\cdots,x_{n-1})$ be the FF of the NFSRs that can generate n-order dBSs. In the study of Walker [6], it was proved that the constant term of the Boolean function g(x1,⋯,xn−1)$g(x_{1},\cdots,x_{n-1})$ must be 1, the number of monomials in g(x1,⋯,xn−1)$g(x_{1},\cdots,x_{n-1})$ is odd, and the algebraic normal form (ANF) of the Boolean function g(x1,⋯,xn−1)$g(x_{1},\cdots,x_{n-1})$ cannot hold all the linear terms x1,x2,⋯,xn−1$x_1,x_2,\cdots,x_{n-1}$; and the study also provided the relationship among g, R(g)=g(xn−1,xn−2,⋯,x1)$R(g)=g(x_{n-1},x_{n-2},\cdots,x_{1})$ and D(g)=f(x1¯,x2¯,⋯,xn−1¯)$D(g)=f(\overline{x_{1}},\overline{x_{2}},\cdots,\overline{x_{n-1}})$ where xi¯=xi+1$\overline{x_{i}}=x_{i}+1$. Calik et al. [7] proved that at least one integer i between 1 and n – 1 exists, such that the number of monomials including x_i in g is even. It is proved in the study of Golomb [4] that the weight of g(x1,⋯,xn−1)$g(x_{1},\cdots,x_{n-1})$ is odd and g contains the term x1x2⋯xn−1$x_1x_2\cdots x_{n-1}$. The bounds of the weight of g were given in Wang et al. [8]. For any integer k, there exists at least one element α in F2n−1$\mathbb{F}_2^{n-1}$ satisfying wt(g)=k$wt(g)=k$ and g(α) = 1 [9]. From the perspective of the relationship between linear terms and quadratic nonlinear terms of g, the authors studied the necessary conditions for FFs of NFSRs that can produce dBSs [10]. The tight limits of the number of ones in the local truth table of the Boolean function g were provided in Tang et al. [11]. In this paper, from the perspective of the relationship among the linear terms, quadratic nonlinear terms and cubic nonlinear terms of g, we propose some necessary conditions for FFs of NFSRs that can generate dBSs.

The rest of this paper is organised as follows. In Section 2, we present a simple introduction of Boolean functions and NFSRs. We also list the known necessary conditions for FFs of NFSRs that can produce dBSs. Section 3 gives some new necessary conditions for FFs of dBSs. Section 4 concludes the work.

Throughout this paper, n is a positive integer and the notation F2n={(x0,x1,x2,⋯,xn−1)∣xi∈F2,i∈{0,1,2,⋯,n−1}}$\mathbb{F}_2^n=\{(x_0,x_1, x_2,\cdots , x_{n-1})\,\mid\, x_i\in \mathbb{F}_2,\,i \in \{0,1, 2,\cdots, n-1\}\}$ denotes an n-dimensional vectorspace over F2$\mathbb{F}_2$.

In the following, let us recall some results on feedback shift registers and Boolean functions.

A mapping from the vectorspace F2n$\mathbb{F}_2^n$ to the field F2$\mathbb{F}_2$ is referred to as an n-variable Boolean function. The notation BFn$\mathscr{BF}_n$ denotes the set that contains all n-variable Boolean functions. Let x be a binary n-length vector; the notation w(t)(x) denotes x’s Hamming weight, which equals the number of nonzero coordinates of x (i.e. the size of the set {i∈{0,1,⋯,n−1}∣xi=1}$\{i \in \{0,1,\cdots, n-1\}\mid x_i=1\}$). For any function f∈BFn$f\in \mathscr{BF}_n$, f’s Hamming weight wt(f) equals the size of {x∈F2n∣f(x)=1}$\{x \in \mathbb{F}_2^n\mid f(x)=1\}$, which is referred to as the support of f [12].

For any f∈BFn$f\in \mathscr{BF}_n$, we know that f has a unique n-variable polynomial representation over the finite field F2$\mathbb{F}_2$, which is referred to as the algebraic normal form (ANF), \begin{align*}f(x_0,x_1, x_2,\cdots , x_{n-1}) &=a_0+\sum\limits_{i=0}^{n-1}a_ix_i+\sum\limits_{0\leq i<j\leq n-1}^{n-1}a_{i,j}x_ix_j\\ &+\sum\limits_{0\leq i<j<k\leq n-1}^{n-1}a_{i,j,k}x_ix_jx_k+\cdots+a_{0,1, \cdots, n-1}x_0x_1\cdots x_{n-1},\end{align*} where the coefficients a0,ai,ai,j,⋯,a0,1,2,⋯,n−1$a_0,a_i,a_{i,j},\cdots,a_{0,1, 2,\cdots, n-1}$ are in the finite field F2$\mathbb{F}_2$ [12]. The largest number of variables in all monomials of f with nonzero coefficient is referred to as the degree of f. Then a₀ is referred to as the constant term of f, aixi(i=0,1,⋯,n−1)$a_ix_i(i=0,1,\cdots,n-1)$ as the linear terms and other terms as the nonlinear terms of f. Let C(f) = a₀ denote the constant term of f, L(f) denote the sum of all linear terms of f and N_i(f) denote the sum of all nonlinear terms of f with degree i. Then, the Boolean function f can be rewritten as f=C(f)+L(f)+∑i=2nNi(f)$f=C(f)+L(f)+\sum\limits_{i=2}^{n}N_i(f)$.

If ∑i=2nNi(f)=0$\sum\limits_{i=2}^{n}N_i(f)=0$, the Boolean function f is affine. Moreover, f is linear when C(f) = 0.

From a Boolean function f∈BFn$f\in\mathscr{BF}_n$ and an initial state (a0,a1,⋯,an−1)∈F2n$(a_0,a_1,\cdots, a_{n-1})\in \mathbb{F}_2^n$, an infinite binary output sequence a=(a0,a1,a2,⋯)${\bf a}=(a_0,a_1,a_2,\cdots)$ satisfying ai+n=f(ai,ai+1,⋯,ai+n−1) for i=0,1,2,⋯,$$a_{i+n}=f(a_i,a_{i+1},\cdots,a_{i+n-1})\,\,\,\text{ for } \,\,\,i=0,1,2,\cdots ,$$ can be obtained by an n-stage feedback shift register (FSR) with FF f. If f is nonlinear, we call the FSR a NFSR.

Otherwise, we call it a LFSR. The notation Ω(f) denotes the set of all such sequences (with 2ⁿ possible initial states) generated by f. The FF f determines the properties of sequences in Ω(f). For a=(a0,a1,a2,⋯)∈Ω(f)${\bf a}=(a_0,a_1,a_2,\cdots)\in \Omega(f)$ and any nonnegative integer i, the shift operator L on Ω(f) can be defined by Lia=(ai,ai+1,ai+2,⋯).$$L^i{\bf a}=(a_i,a_{i+1},a_{i+2},\cdots).$$

The smallest integer r such that a=Lra${\bf a}=L^r{\bf a}$ is referred to as the period of a, which is expressed by per(a). If the FF f is nonsingular (which means that f(x0,x1,⋯,xn−1)=x0+g(x1,⋯,xn−1)$$f(x_0,x_1,\cdots,x_{n-1})=x_0+g(x_{1},\cdots,x_{n-1})$$ for a Boolean function g∈BFn−1$g\in \mathscr{BF}_{n-1}$), all sequences in Ω(f) are periodic, and the reverse is also true [4]. Throughout this paper, we assume that the FFs are all nonsingular.

The period of output sequence from each n-stage FSR is at most 2ⁿ. If this upper bound is attained, this sequence is referred to as a de Bruijn sequence. Let R(f)=f(xn−1,xn−2,⋯,x1,x0) and D(f)=f(x0¯,x1¯,x2¯,⋯,xn−1¯),$$R(f) = f({x_{n - 1}},{x_{n - 2}}, \cdots ,{x_1},{x_0}){\rm{ and }}D(f) = f(\overline {{x_0}} ,\overline {{x_1}} ,\overline {{x_2}} , \cdots ,\overline {{x_{n - 1}}} ),$$ where xi¯=xi+1$\overline{x_{i}}=x_{i}+1$. We recollect some related properties about dBS as follows.

Lemma 1. Let n > 2 and f be the FF of an n-stage FSR. If f generates a dBS, then x0+R(g)$x_0+R(g)$, x0+D(g)$x_0+D(g)$ and x0+D(R(g))$x_0+D(R(g))$ can also generate dBS [6].

We review the known necessary conditions for FFs of NFSRs, which can produce dBSs. We copy their list into the following theorem.

Theorem 2. For a Boolean function g∈BFn−1$g\in \mathscr{BF}_{n-1}$, let f(x0,x1,⋯,xn−1)=x0+g(x1,⋯,xn−1)$f(x_0,x_1,\cdots,x_{n-1})=x_0+g(x_{1},\cdots,x_{n-1})$ be a FF of an n-stage FSR, which can generate a dBS. Then

g(0,0,⋯,0)=1$g(0,0,\cdots,0)=1$, i.e., C(g)=1$C(g)=1$ [6].

With the above preparation, we will investigate the necessary conditions for FFs of NFSRs corresponding to dBS in the next section.

In this section, we consider some new necessary conditions for FFs of NFSRs that can produce dBSs.

Theorem 3. If n≥6$n\geq 6$ and g∈BFn−1$g\in \mathscr{BF}_{n-1}$, let f(x0,x1,⋯,xn−1)=x0+g(x1,⋯,xn−1)$f(x_0,x_1,\cdots,x_{n-1})=x_0+g(x_{1},\cdots,x_{n-1})$ be a FF of an n-stage FSR, which can generate a dBS. If L(g)=0$L(g)=0$, then

at least one of the nonlinear terms x1x3,x2x4,⋯,xn−3xn−1$x_1x_3,x_2x_4,\cdots,x_{n-3}x_{n-1}$ does not occur in g’s ANF;

Proof. We only provide the proof for case (1) here, since other cases can be shown by using a similar method.

Suppose that g contains all the terms x1x3,x2x4,⋯,xn−3xn−1$x_1x_3,x_2x_4,\cdots,x_{n-3}x_{n-1}$. By L(g) = 0, we have g(1,0,0,⋯,0⏟n−2)=g(0,0,⋯,0⏟n−2,1)=1,$$g(1,\underbrace{0,0,\cdots,0}_{n-2})=g(\underbrace{0,0,\cdots,0}_{n-2},1)=1,$$ g(0,0,⋯,0⏟n−3,1,0)=g(0,1,0,0,⋯,0⏟n−3)=1$$g(\underbrace{0,0,\cdots,0}_{n-3},1,0)=g(0,1,\underbrace{0,0,\cdots,0}_{n-3})=1$$ and g(0,0,⋯,0⏟i−1,1,0,1,0,0,⋯,0⏟n−i−3)=0$$g(\underbrace{0,0,\cdots,0}_{i-1},1,0,1,\underbrace{0,0,\cdots,0}_{n-i-3})=0$$ for any i=1,2,⋯,n−3$i=1,2,\cdots,n-3$. Thus, f generates the sequence a=(0,0,⋯,0⏟n−2,1,0,1,0,0,⋯,0⏟n−2,1,0,1,⋯)$${\bf a}=(\underbrace{0,0,\cdots,0}_{n-2},1,0,1,\underbrace{0,0,\cdots,0}_{n-2},1,0,1,\cdots)$$ where per(a)=n+1<2n$per({\bf a})=n+1<2^n$ which contradicts the condition that a dBS can be generated by NFSRs with the FF f [4]. Thus, we can complete the proof.

It is worth noting that the new necessary conditions in Theorem 3 cannot be inferred from the conditions in Theorem 2. This fact is demonstrated in the following Example 4.

Example 4. (1) For the Boolean function g1(x1,x2,x3,x4,x5)=1+x1x3+x2x4+x3x5+x1x2+x1x2x3+x1x2x3x4x5$g_1(x_1,x_2,x_3,x_4,x_5)=1+x_1x_3+x_2x_4+x_3x_5+x_1x_2+x_1x_2x_3+x_1x_2x_3x_4x_5$ let f1(x0,x1,x2,x3,x4,x5)=x0+g1(x1,x2,x3,x4,x5)$$f_1(x_0,x_1,x_2,x_3,x_4,x_5)=x_0+g_1(x_1,x_2,x_3,x_4,x_5)$$ be the FF of a six-stage NFSR. It can be inspected that f1(x0,x1,x2,x3,x4,x5)$f_1(x_0,x_1,x_2,x_3,x_4,x_5)$ meets all conditions that are given in Theorem 2 [4, 6–11]. In addition, it contains all terms in {x1x3,x2x4,x3x5}$\{x_1x_3,\,x_2x_4,\,x_3x_5\}$ with L(g1)=0$L(g_1)=0$. Moreover, computer software verifies that this NFSR cannot produce a dBS.

(2) For the Boolean function g2(x1,x2,x3,x4,x5)=1+x1x3+x2x5+x1x5+x1x2+x1x2x3+x1x2x3x4x5$g_2(x_1,x_2,x_3,x_4,x_5)=1+x_1x_3+x_2x_5+x_1x_5+x_1x_2+x_1x_2x_3+x_1x_2x_3x_4x_5$ let f2(x0,x1,x2,x3,x4,x5)=x0+g2(x1,x2,x3,x4,x5)$$f_2(x_0,x_1,x_2,x_3,x_4,x_5)=x_0+g_2(x_1,x_2,x_3,x_4,x_5)$$ be the FF of a six-stage NFSR. It can be inspected that f2(x0,x1,x2,x3,x4,x5)$f_2(x_0,x_1,x_2,x_3,x_4,x_5)$ meets all conditions that are given in Theorem 2 [4, 6–11] and the case (1) of Theorem 3. In addition, f₂ contains all the terms in {x1x4,x2x5,x1x5}$\{x_1x_4,\,x_2x_5,\,x_1x_5\}$ with L(g2)=0$L(g_2)=0$. Moreover, computer software verifies that this NFSR cannot produce a dBS.

Theorem 5. If n≥6$n\geq 6$, for a Boolean function g∈BFn−1$g\in \mathscr{BF}_{n-1}$, assume that f(x0,x1,⋯,xn−1)=x0+g(x1,⋯,xn−1)$f(x_0,x_1,\cdots,x_{n-1})=x_0+g(x_{1},\cdots,x_{n-1})$ is the FF of an n-stage FSR that can generate a dBS. Suppose L(g) = 0.

(1) For N2(g)=∑i=2n−3xixi+1$N_2(g)=\sum\limits_{i=2}^{n-3}x_ix_{i+1}$, if x1x2x3$x_1x_2x_3$ and xn−3xn−2xn−1$x_{n-3}x_{n-2}x_{n-1}$ do not occur in g’s ANF, at least one of the nonlinear x2x3x4,x3x4x5,⋯,xn−4xn−3xn−2$$x_2x_3x_4,x_3x_4x_5,\cdots,x_{n-4}x_{n-3}x_{n-2}$$ does not occur in g’s ANF.

(2) For N2(g)=0$N_2(g)=0$, then at least one of the terms x1x2x3,x2x3x4,x3x4x5,⋯,xn−3xn−2xn−1$$x_1x_2x_3,x_2x_3x_4,x_3x_4x_5,\cdots,x_{n-3}x_{n-2}x_{n-1}$$ does not occur in g’s ANF.

Proof. If x1x2x3$x_1x_2x_3$ and xn−3xn−2xn−1$x_{n-3}x_{n-2}x_{n-1}$ do not occur in g’s ANF, suppose that g contains all the terms x2x3x4,x3x4x5,⋯,xn−4xn−3xn−2.$$x_2x_3x_4,x_3x_4x_5,\cdots,x_{n-4}x_{n-3}x_{n-2}.$$

By L(g) = 0 and N2(g)=∑i=2n−3xixi+1$N_2(g)=\sum\limits_{i=2}^{n-3}x_ix_{i+1}$, we have g(1,0,0,⋯,0⏟n−2)=g(0,0,⋯,0⏟n−2,1)=g(0,0,⋯,0⏟n−1)=g(1,1,0,0,⋯,0⏟n−3)=1$$g(1,\underbrace{0,0,\cdots,0}_{n-2})=g(\underbrace{0,0,\cdots,0}_{n-2},1)=g(\underbrace{0,0,\cdots,0}_{n-1})=g(1,1,\underbrace{0,0,\cdots,0}_{n-3})=1$$ and g(0,0,⋯,0⏟i−1,1,1,1,0,0,⋯,0⏟n−i−3)=0$$g(\underbrace{0,0,\cdots,0}_{i-1},1,1,1,\underbrace{0,0,\cdots,0}_{n-i-3})=0$$ for any i=1,2,⋯,n−3$i=1,2,\cdots,n-3$. Thus, f generate the sequence a=(0,0,⋯,0⏟n,1,1,1,0,0,⋯,0⏟n,1,1,1,⋯)$${\bf a}=(\underbrace{0,0,\cdots,0}_{n},1,1,1,\underbrace{0,0,\cdots,0}_{n},1,1,1,\cdots)$$ where per(a)=n+3<2n$per(a)=n+3<2^n$ which contradicts the condition that a dBS can be generated by NFSRs with the FF f [4]. Thus, we can complete the proof of case (1).

Using the same method we can obtain the case (2), and thus we omit the proof here.

Note that the new necessary conditions in Theorem 5 cannot be inferred from the conditions in Theorems 2 and 3. This fact can be demonstrated in the following Example 6.

Example 6. (1) For g1(x1,x2,x3,x4,x5)=1+x3(x2+x4)+(x1+x2)x3x4+x1x2x3x4(1+x5)$g_1(x_1,x_2,x_3,x_4,x_5)=1+x_3(x_2+x_4)+(x_1+x_2)x_3x_4+x_1x_2x_3x_4(1+x_5)$, let f1(x0,x1,x2,x3,x4$f_1(x_0,x_1,x_2,x_3,x_4$, x5)=x0+g1(x1,x2,x3,x4,x5)$x_5)=x_0+g_1(x_1,x_2,x_3,x_4,x_5)$ be the FF of a six-stage NFSR. It can be inspected that f1(x0,x1,x2,x3,x4,x5)$f_1(x_0,x_1,x_2,x_3,x_4,x_5)$ meets all conditions that are given in Theorems 2 and 3. In addition, f₁ does not contain x1x2x3$x_1x_2x_3$ and x3x4x5$x_{3}x_{4}x_{5}$, but contains terms x2x3x4$x_2x_3x_4$ with L(g) = 0 and N2(g)=x2x3+x3x4$N_2(g)=x_2x_3+x_3x_4$. Moreover, computer software verifies that this NFSR cannot produce a dBS.

(2) For g2(x1,x2,x3,x4)=1+x1x2x3+x2x3x4+x3x4x5+x1x2x5+x1x3x5+x1x2x3x4x5,$g_2(x_1,x_2,x_3,x_4)=1+x_1x_2x_3+x_2x_3x_4+x_3x_4x_5+x_1x_2x_5+x_1x_3x_5+x_1x_2x_3x_4x_5,$ let f2(x0,x1,x2,x3,x4$f_2(x_0,x_1,x_2,x_3,x_4$, x5)=x0+g(x1,x2,x3,x4,x5)$x_5)=x_0+g(x_1,x_2,x_3,x_4,x_5)$ be the FF of a six-stage NFS. It can be inspected that f2(x0,x1,x2,x3,x4,x5)$f_2(x_0,x_1,x_2,x_3,x_4,x_5)$ meets all conditions that are given in Theorems 2 and 3. In addition, f₂ contains terms x1x2x3,x2x3x4,x3x4x5$x_1x_2x_3,x_2x_3x_4,x_3x_4x_5$ with L(g) = 0 and N2(g)=0$N_2(g)=0$. Moreover, computer software verifies that this NFSR cannot produce a dBS.

In the following, we consider the cases for L(g)≠0$L(g)\neq 0$.

Theorem 7. If n≥6$n\geq 6$ and g∈BFn−1$g\in \mathscr{BF}_{n-1}$, assume that f(x0,x1,⋯,xn−1)=x0+g(x1,⋯,xn−1)$f(x_0,x_1,\cdots,x_{n-1})=x_0+g(x_{1},\cdots,x_{n-1})$ is the FF of an n-stage FSR that can generate a dBS. For L(g)=∑i=2n−2xi$L(g)=\sum\limits_{i=2}^{n-2}x_i$, if x1x2$x_1x_2$ and xn−2xn−1$x_{n-2}x_{n-1}$ do not occur in g’s ANF, then at least one of the nonlinear terms x2x3,x3x4,⋯,xn−3xn−2$$x_2x_3,x_3x_4,\cdots,x_{n-3}x_{n-2}$$ does not occur in g’s ANF.

Proof. If x₁x₂ and xn−2xn−1$x_{n-2}x_{n-1}$ do not occur in g’s ANF, suppose that g contains all the terms x2x3,x3x4,⋯,xn−3xn−2$x_2x_3,x_3x_4,\cdots,x_{n-3}x_{n-2}$.

By L(g)=∑i=2n−2xi$L(g)=\sum\limits_{i=2}^{n-2}x_i$, we have g(1,0,0,⋯,0⏟n−2)=g(0,0,⋯,0⏟n−2,1)=g(0,0,⋯,0⏟n−1)=1$$g(1,\underbrace{0,0,\cdots,0}_{n-2})=g(\underbrace{0,0,\cdots,0}_{n-2},1)=g(\underbrace{0,0,\cdots,0}_{n-1})=1$$ and g(0,0,⋯,0⏟i−1,1,1,0,0,⋯,0⏟n−i−2)=0$$g(\underbrace{0,0,\cdots,0}_{i-1},1,1,\underbrace{0,0,\cdots,0}_{n-i-2})=0$$ for any i=1,2,⋯,n−3$i=1,2,\cdots,n-3$. Thus, f generates the sequence a=(0,0,⋯,0⏟n,1,1,0,0,⋯,0⏟n,1,1,⋯)$${\bf a}=(\underbrace{0,0,\cdots,0}_{n},1,1,\underbrace{0,0,\cdots,0}_{n},1,1,\cdots)$$ where per(a)=n+2<2n$per(a)=n+2<2^n$, which contradicts the condition that a dBS can be generated by NFSRs with the FF f [4]. Thus, we can complete the proof.

From the following Example 8, we can indicate that the conditions in Theorem 2 cannot deduce the necessary condition in Theorem 7.

Example 8. For g∈BF5$g\in \mathscr{BF}_{5}$ and g(x1,x2,x3,x4,x5)=1+∑i=24xi+x2x3+x3x4+x1x4+x1x2x5(1+x3x4),$$g(x_1,x_2,x_3,x_4,x_5)=1+\sum\limits_{i=2}^4x_i+x_2x_3+x_3x_4+x_1x_4+x_1x_2x_5(1+x_3x_4),$$ let f(x0,x1,x2,x3,x4,x5)=x0+g1(x1,x2,x3,x4,x5)$f(x_0,x_1,x_2,x_3,x_4,x_5)=x_0+g_1(x_1,x_2,x_3,x_4,x_5)$ be the FF of a six-stage NFSR. Note that f meets all conditions that are listed in Theorem 2, f does not contain any term in {x1x2,x4x5}$\{x_1x_2,\,x_{4}x_{5}\}$ and contains all terms in {x2x3,x3x4}$\{x_2x_3,\,x_3x_4\}$ with L(g)=x2+x3+x4$L(g)=x_2+x_3+x_4$. It can be verified that f cannot generate a dBS by computer that is consistent with Theorem 7.

Theorem 9. If n≥5$n\geq 5$, for a Boolean function g∈BFn−1$g\in \mathscr{BF}_{n-1}$, assume that f(x0,x1,⋯,xn−1)=x0+g(x1,⋯,xn−1)$f(x_0,x_1,\cdots,x_{n-1})=x_0+g(x_{1},\cdots,x_{n-1})$ is the FF of an n-stage FSR that can generate a dBS. For L(g)=x2$L(g)=x_2$ and N2(g)=x1x2+x2x3$N_2(g)=x_1x_2+x_2x_3$, if x1x2x3$x_1x_2x_3$ does not occur in g’s ANF, at least one of the nonlinear terms x2x3x4,x3x4x5,⋯,xn−3xn−2xn−1$x_2x_3x_4,x_3x_4x_5,\cdots,x_{n-3}x_{n-2}x_{n-1}$ does not occur in g’s ANF.

Proof. If x1x2x3$x_1x_2x_3$ does not occur in g’s ANF, suppose g contains all terms x2x3x4,x3x4x5,⋯,xn−3xn−2xn−1.$$x_2x_3x_4,x_3x_4x_5,\cdots,x_{n-3}x_{n-2}x_{n-1}.$$

By L(g)=x2$L(g)=x_2$ and N2(g)=x1x2+x2x3$N_2(g)=x_1x_2+x_2x_3$, we have g(1,0,0,⋯,0⏟n−2)=g(0,0,⋯,0⏟n−2,1)=g(0,0,⋯,0⏟n−1)=g(1,1,0,0,⋯,0⏟n−3)=1$$g(1,\underbrace{0,0,\cdots,0}_{n-2})=g(\underbrace{0,0,\cdots,0}_{n-2},1)=g(\underbrace{0,0,\cdots,0}_{n-1})=g(1,1,\underbrace{0,0,\cdots,0}_{n-3})=1$$ and g(0,0,⋯,0⏟i−1,1,1,1,0,0,⋯,0⏟n−i−3)=0$$g(\underbrace{0,0,\cdots,0}_{i-1},1,1,1,\underbrace{0,0,\cdots,0}_{n-i-3})=0$$ for any i=1,2,⋯,n−3$i=1,2,\cdots,n-3$. Thus, f generates the sequence a=(0,0,⋯,0⏟n,1,1,1,0,0,⋯,0⏟n,1,1,1,⋯)$${\bf a}=(\underbrace{0,0,\cdots,0}_{n},1,1,1,\underbrace{0,0,\cdots,0}_{n},1,1,1,\cdots)$$ where per(a)=n+3<2n$per(a)=n+3<2^n$, which contradicts the condition that a dBS can be produced by the NFSR with the FF f [4]. Thus, the proof is completed.

The following Example 10 indicates that the new necessary condition in Theorem 9 cannot be inferred from the conditions in Theorem 2.

Example 10. For g(x1,x2,x3,x4,x5)=1+x2+x1x2+x2x3+x2x3x4+x3x4x5+x1x2x3x4x5,$g(x_1,x_2,x_3,x_4,x_5)=1+x_2+x_1x_2+x_2x_3+x_2x_3x_4+x_3x_4x_5+x_1x_2x_3x_4x_5,$ let f(x0,x1,x2,x3,x4$f(x_0,x_1,x_2,x_3,x_4$, x5)=x0+g(x1,x2,x3,x4,x5)$x_5)=x_0+g(x_1,x_2,x_3,x_4,x_5)$ be the FF of a six-stage NFSR. It can be inspected that f(x0,x1,x2,x3,x4,x5)$f(x_0,x_1,x_2,x_3,x_4,x_5)$ meets all conditions that are listed in Theorem 2. In addition, f does not contain x1x2x3$x_1x_2x_3$ and contains all terms in {x2x3x4,x3x4x5}$\{x_2x_3x_4,\,x_3x_4x_5\}$ with L(g)=x2$L(g)=x_2$ and N2(g)=x1x2+x2x3$N_2(g)=x_1x_2+x_2x_3$. Moreover, computer software verifies that this NFSR cannot produce a dBS.

Theorem 11. If n≥5$n\geq 5$ and g∈BFn−1$g\in \mathscr{BF}_{n-1}$, assume that f(x0,x1,⋯,xn−1)=x0+g(x1,⋯,xn−1)$f(x_0,x_1,\cdots,x_{n-1})=x_0+g(x_{1},\cdots,x_{n-1})$ is the FF of an n-stage FSR that can generate a dBS. For L(g)=xn−2$L(g)=x_{n-2}$ and N2(g)=xn−3xn−2+xn−2xn−1$N_2(g)=x_{n-3}x_{n-2}+x_{n-2}x_{n-1}$, if xn−3xn−2xn−1$x_{n-3}x_{n-2}x_{n-1}$ does not occur in g’s ANF, at least one of the nonlinear terms x1x2x3,x2x3x4,x3x4x5,⋯,xn−4xn−3xn−2$$x_1x_2x_3,x_2x_3x_4,x_3x_4x_5,\cdots,x_{n-4}x_{n-3}x_{n-2}$$ does not occur in g’s ANF.

Proof. Because f is the FF of an n-stage FSR that can generate a dBS, by Lemma 1, a dBS can be generated by the NFSR with the FF x0+R(g)$x_0+R(g)$. Because L(g)=xn−2$L(g)=x_{n-2}$, then L(R(g))=x2$L(R(g))=x_2$. If xn−3xn−2xn−1$x_{n-3}x_{n-2}x_{n-1}$ does not occur in g, suppose all terms x1x2x3,x2x3x4,⋯,xn−4xn−3xn−2$$x_1x_2x_3,x_2x_3x_4,\cdots,x_{n-4}x_{n-3}x_{n-2}$$ occur in g’s ANF, then x1x2x3$x_1x_2x_3$ does not occur in R(g)’s ANF and all terms x1x2x3,x2x3x4,⋯,xn−4xn−3xn−2$$x_2x_3x_4,x_3x_4x_5,\cdots,x_{n-3}x_{n-2}x_{n-1}$$ occur in R(g)’s ANF, which contradicts the conclusion of Theorem 9. Thus, the desired conclusion can be obtained.

The following Example 12 can show that the conditions in Theorem 2 cannot deduce the new necessary condition in Theorem 11.

Example 12. For g(x1,x2,x3,x4,x5)=1+x4+x3x4+x4x5+x1x2x3+x2x3x4+x1x2x3x4x5,$$g(x_1,x_2,x_3,x_4,x_5)=1+x_4+x_3x_4+x_4x_5+x_1x_2x_3+x_2x_3x_4+x_1x_2x_3x_4x_5,$$ let f(x0,x1,x2,x3,x4,x5)=x0+g(x1,x2,x3,x4,x5)$f(x_0,x_1,x_2,x_3,x_4,x_5)=x_0+g(x_1,x_2,x_3,x_4,x_5)$ be the FF of a six-stage NFSR. It can be inspected that f meets all conditions that are given in Theorem 2. In addition, f does not contain x3x4x5$x_3x_4x_5$ and contains all terms in {x1x2x3,x2x3x4}$\{x_1x_2x_3,\,x_2x_3x_4\}$ with L(g)=x4$L(g)=x_4$ and N2(g)=x3x4+x4x5$N_2(g)=x_3x_4+x_4x_5$. Moreover, computer software verifies that this NFSR cannot produce a dBS.

Theorem 13. If 2∣n$2 \mid n$ and n≥6$n\geq 6$, for a Boolean function g∈BFn−1$g\in \mathscr{BF}_{n-1}$ assume that f(x0,x1,⋯,xn−1)=x0+g(x1,⋯,xn−1)$f(x_0,x_1,\cdots,x_{n-1})=x_0+g(x_{1},\cdots,x_{n-1})$ is the FF of an n-stage FSR which can generate a dBS. Assume that L(g)=x1+x3+⋯+xn−1$L(g)=x_1+x_3+\cdots+x_{n-1}$, then at least one of the nonlinear terms x1x3,x2x4,x3x5,⋯,xn−3xn−1$x_1x_3,x_2x_4,x_3x_5,\cdots,x_{n-3}x_{n-1}$ do not occur in g’s ANF.

Proof. If n is even, suppose all terms x1x3,x2x4,x3x5,⋯,xn−3xn−1$x_1x_3,x_2x_4,x_3x_5,\cdots,x_{n-3}x_{n-1}$ occur in the ANF of g. By L(g)=x1+x3+⋯+xn−1$L(g)=x_1+x_3+\cdots+x_{n-1}$, we have g(1,0,0,⋯,0⏟n−2)=g(0,0,⋯,0⏟n−2,1)=0,$$g(1,\underbrace{0,0,\cdots,0}_{n-2})=g(\underbrace{0,0,\cdots,0}_{n-2},1)=0,$$ g(0,1,0,0,⋯,0⏟n−3)=g(0,0,⋯,0⏟n−3,1,0)=1,$$g(0,1,\underbrace{0,0,\cdots,0}_{n-3})=g(\underbrace{0,0,\cdots,0}_{n-3},1,0)=1,$$ g(0,0,⋯,0⏟i−1,1,0,1,0,0,⋯,0⏟n−i−3)=0$$g(\underbrace{0,0,\cdots,0}_{i-1},1,0,1,\underbrace{0,0,\cdots,0}_{n-i-3})=0$$ for any i=1,2,⋯,n−3$i=1,2,\cdots,n-3$. Thus, f generates the sequence a=(0,0,⋯,0⏟n−2,1,0,1,0,0,⋯,0⏟n−2,1,0,1,⋯)$${\bf a}=(\underbrace{0,0,\cdots,0}_{n},1,0,1,\underbrace{0,0,\cdots,0}_{n},1,0,1,\cdots)$$ where per(a)=n+3<2n$per(a)=n+3<2^n$, which contradicts the condition that a dBS can be constructed by the n-stage FSR with the FF f [4].

The following Example 14 can indicate that the conditions in Theorem 2 cannot deduce the new necessary condition in Theorem 13.

Example 14. For g(x1,x2,x3,x4,x5)=1+x1+x3+x5+x1x3+x2x4+x3x5+x1x4+x1x2x3x4x5,$$g(x_1,x_2,x_3,x_4,x_5)=1+x_1+x_3+x_5+x_1x_3+x_2x_4+x_3x_5+x_1x_4+x_1x_2x_3x_4x_5,$$ let f(x0,x1,x2,x3,x4,x5)=x0+g(x1,x2,x3,x4,x5)$f(x_0,x_1,x_2,x_3,x_4,x_5)=x_0+g(x_1,x_2,x_3,x_4,x_5)$ be the FF of a six-stage NFSR. It can be inspected that f satisfies all conditions that are listed in Theorem 2. In addition, f contains terms x1x3,x2x4,x3x5$x_1x_3,x_2x_4,x_3x_5$ with L(g)=x1+x3+x5$L(g)=x_1+x_3+x_5$. Moreover, computer software verifies that this NFSR cannot produce a dBS.

Theorem 15. If n≥6$n\geq 6$, for a Boolean function g∈BFn−1$g\in \mathscr{BF}_{n-1}$, assume that f(x0,x1,⋯,xn−1)=x0+g(x1,⋯,xn−1)$f(x_0,x_1,\cdots,x_{n-1})=x_0+g(x_{1},\cdots,x_{n-1})$ is the FF of an n-stage FSR that can generate a dBS. For L(g)=∑i=3n−2xi$L(g)=\sum\limits_{i=3}^{n-2}x_i$ and N2(g)=∑i=3n−3xixi+2$N_2(g)=\sum\limits_{i=3}^{n-3}x_ix_{i+2}$, if x1x2x3$x_1x_2x_3$ and xn−4xn−3xn−2$x_{n-4}x_{n-3}x_{n-2}$ do not occur in g’s ANF, at least one of the nonlinear terms x2x3x4,x3x4x5,⋯,xn−5xn−4xn−3,xn−3xn−2xn−1$$x_2x_3x_4,x_3x_4x_5,\cdots,x_{n-5}x_{n-4}x_{n-3},x_{n-3}x_{n-2}x_{n-1}$$ do not occur in g’s ANF.

Proof. If x1x2x3$x_1x_2x_3$ and xn−4xn−3xn−2$x_{n-4}x_{n-3}x_{n-2}$ do not occur in g’s ANF, suppose all terms x2x3x4,x3x4x5,⋯,xn−5xn−4xn−3,xn−3xn−2xn−1$$x_2x_3x_4,x_3x_4x_5,\cdots,x_{n-5}x_{n-4}x_{n-3},x_{n-3}x_{n-2}x_{n-1}$$ occur in g’s ANF. By L(g)=∑i=3n−2xi$L(g)=\sum\limits_{i=3}^{n-2}x_i$ and N2(g)=∑i=3n−3xixi+2$N_2(g)=\sum\limits_{i=3}^{n-3}x_ix_{i+2}$, we have g(1,0,0,⋯,0⏟n−2)=g(0,0,⋯,0⏟n−2,1)=g(0,0,⋯,0⏟n−1)=g(1,1,0,0,⋯,0⏟n−3)=1$$g(1,\underbrace{0,0,\cdots,0}_{n-2})=g(\underbrace{0,0,\cdots,0}_{n-2},1)=g(\underbrace{0,0,\cdots,0}_{n-1})=g(1,1,\underbrace{0,0,\cdots,0}_{n-3})=1$$ and g(0,0,⋯,0⏟i−1,1,1,1,0,0,⋯,0⏟n−i−3)=0$$g(\underbrace{0,0,\cdots,0}_{i-1},1,1,1,\underbrace{0,0,\cdots,0}_{n-i-3})=0$$ for any i=1,2,⋯,n−3$i=1,2,\cdots,n-3$. Thus, f generates the sequence a=(0,0,⋯,0⏟n,1,1,1,0,0,⋯,0⏟n,1,1,1,⋯)$${\bf a}=(\underbrace{0,0,\cdots,0}_{n},1,1,1,\underbrace{0,0,\cdots,0}_{n},1,1,1,\cdots)$$ where per(a)=n+3<2n$per(a)=n+3<2^n$, which contradicts the condition that a dBS can be constructed by the n-stage FSR with the FF f [4]. Thus, the proof can be obtained.