Detalles de la revista
Formato
Revista
eISSN
2444-8656
Primera edición
01 Jan 2016
Calendario de la edición
2 veces al año
Idiomas
Inglés
Acceso abierto

Some Necessary Conditions for Feedback Functions of de Bruijn Sequences

Recibido: 14 Jun 2022
Detalles de la revista
Formato
Revista
eISSN
2444-8656
Primera edición
01 Jan 2016
Calendario de la edición
2 veces al año
Idiomas
Inglés
Introduction

For a positive integer n, an n-order binary de Bruijn sequence (dBS) is a binary periodic sequence of period 2n, 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 [25]. 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 xi 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.

Preliminaries

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), $f(x0,x1,x2,⋯,xn−1)=a0+∑i=0n−1aixi+∑0≤i\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 a0 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) = a0 denote the constant term of f, L(f) denote the sum of all linear terms of f and Ni(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 $$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 2n 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 2n. If this upper bound is attained, this sequence is referred to as a de Bruijn sequence. Let $$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].

$g(1,1,⋯,1)=1$$g(1,1,\cdots,1)=1$, therefore the number of monomials in g is odd [6].

all linear terms $x1,⋯,xn−1$$x_1,\cdots,x_{n-1}$ are not completely included in g, i.e., $L(g)≠∑i=1n−1xi$$L(g)\neq \sum\limits_{i=1}^{n-1}x_i$ [6].

if n > 2, then neither R(g) nor D(g) is equal to g. Further, $R(g)≠D(g)$$R(g)\neq D(g)$ for even n [6].

for any $i=1,2,⋯,n−1$$i=1,2,\cdots,n-1$, the notation ni denotes the number of monomials including xi in g. Then there exists at least one even number ni [7].

the Boolean function g contains the term $x1x2⋯xn−1$$x_1x_2\cdots x_{n-1}$ and wt(g) is odd [4].

wt(g) satisfies the following inequality $Zn−1≤wt(g)≤2n−1−Zn∗+1,$$$Z_n-1\leq wt(g)\leq 2^{n-1}-Z_n^*+1,$$ where $Zn=1n∑d|nϕ(d)2nd$$Z_n=\frac{1}{n}\sum\limits_{d|n}\phi(d)2^{\frac{n}{d}}$ and $Zn∗=Zn2−12n∑2d|nϕ(2d)2n2d$$Z_n^*=\frac{Z_n}{2}-\frac{1}{2n}\sum\limits_{2d|n}\phi(2d)2^{\frac{n}{2d}}$ and φ is the Euler function [8].

For any nonnegative integer k, there exists at least one vector $α=(a1,a2,⋯,an−1)∈F2n−1$$\alpha=(a_1,a_2,\cdots,a_{n-1})\in \mathbb{F}_2^{n-1}$ such that $g(α)=1$$g(\alpha)=1$ and $wt(α)=k$$wt(\alpha)=k$ [9].

if n > 2 and L(g) = 0, then g does not contain all the terms $x1x2,x2x3,⋯,xn−2xn−1$$x_1x_2,x_2x_3,\cdots,x_{n-2}x_{n-1}$ [10].

let n > 2 and $L(g)=∑i=1n−2xi$$L(g)=\sum\limits_{i=1}^{n-2}x_i$ [10]. If g does not contain $xn−2xn−1$$x_{n-2}x_{n-1}$, then g does not contain all the terms $x1x2,x2x3,⋯,xn−3xn−2$$x_1x_2,x_2x_3,\cdots,x_{n-3}x_{n-2}$

let n > 2 and $L(g)=∑i=2n−1xi$$L(g)=\sum\limits_{i=2}^{n-1}x_i$ [10]. If g does not contain x1x2, then g does not contain all the terms $x2x3,x3x4,⋯,xn−2xn−1$$x_2x_3,x_3x_4,\cdots,x_{n-2}x_{n-1}$

let n > 3. For any integer k, let $Mk={(0,0,⋯,0⏟i,1,0,0,⋯,0⏟k,1,0,0,⋯,0⏟n−k−i−3,)|0≤i≤n−k−3}$$$M_k=\{(\underbrace{0,0,\cdots,0}_i,1,\underbrace{0,0,\cdots,0}_k,1,\underbrace{0,0,\cdots,0}_{n-k-i-3},)|0\leq i \leq n-k-3\}$$ where $1≤k≤n−12$$1\leq k\leq \frac{n-1}{2}$. If $L(g)=∑i=1kxi+∑i=n−kn−1xi$$L(g)=\sum\limits_{i=1}^{k}x_i+\sum\limits_{i=n-k}^{n-1}x_i$, there is at least one vector $(a1,a2,⋯,an−1)∈Mk$$(a_1,a_2,\cdots,a_{n-1})\in M_k$ such that $g(a1,a2,⋯,an−1)=1$$g(a_1,a_2,\cdots,a_{n-1})=1$ [10].

let $wti(g)$$wt_i(g)$ denote the weight of g on ${(a1,a2,⋯,an−1)∈F2n−1|wt(a1,a2,⋯,an−1)=i}.$$$\{(a_1,a_2,\cdots,a_{n-1})\in \mathbb{F}_2^{n-1}| wt(a_1,a_2,\cdots,a_{n-1})=i\}.$$

Then, for two integers $k1,k2$$k_1,k_2$ satisfying $0≤k1$0\leq k_1 < k_2 \leq n-1$, we have $∑i=k1k2wti(g)≥∑i=k1+1k2Nin+1,$$$\sum\limits_{i=k_1}^{k_2}wt_i(g)\geq \sum\limits_{i=k_1+1}^{k_2}N_i^n+1,$$ where $Nkn=∑r|drn⋅∑s|drμ(s)(n/rsk/rs)$$N_k^n=\sum\limits_{r|d}\frac{r}{n}\cdot \sum\limits_{s|\frac{d}{r}}\mu(s)\binom{n/rs }{k/rs}$, $d=gcd(n,k)$$d={\rm gcd}(n,k)$ and μ is the Mӧbius function [11].

for positive integers $n,e,n′,t$$n,\,e,\,n',\,t$ such that $n=2en′$$n=2^en'$, $gcd(2,n′)=1$${\rm gcd}(2,n')=1$ and $1≤t≤⌊n−12⌋$$1\leq t \leq \lfloor\frac{n-1}{2}\rfloor$, let $GCn$$G_{C_n}$ denote the state graph of the n-stage complemented cycling shift register. Then $∑i=tn−t−1wti(g)≤∑i=tn−t−1(n−1i)−∑i=t⌊n−12⌋Min,$$$\sum\limits_{i=t}^{n-t-1}wt_i(g)\leq \sum\limits_{i=t}^{n-t-1}\binom{n-1 }{i}-\sum\limits_{i=t}^{\lfloor\frac{n-1}{2}\rfloor}M_i^n,$$ where the notation $Min$$M_i^n$ denotes the number of cycles in $⋃d|n′Fin(2e+1d)$$\bigcup\limits_{d|n'}F_i^n(2^{e+1}d)$ with $Fin(2e+1d)={(S0,S1,⋯,ST−1)∈GCn|T=2e+1dandmin0≤j≤T−1wt(Sj)=i}$$F_i^n(2^{e+1}d)=\{(S_0,S_1,\cdots,S_{T-1})\in G_{C_n}|T=2^{e+1}d {\rm and} \min\limits_{0\leq j \leq T-1}{wt(S_j)}=i \}$.

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

Some new necessary conditions

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;

at least one of the nonlinear terms $x1x4,x2x5,⋯,xn−4xn−1,x1xn−1$$x_1x_4,x_2x_5,\cdots,x_{n-4}x_{n-1},x_{1}x_{n-1}$ does not occur in g’s ANF;

at least one of the nonlinear terms $x1x5,x2x6,⋯,xn−5xn−1,x1xn−2,x2xn−1$$$x_1x_5,x_2x_6,\cdots,x_{n-5}x_{n-1},x_{1}x_{n-2},x_{2}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, f2 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, f1 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, f2 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 x1x2 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.

The following Example 16 indicates that the conditions in Theorem 2 cannot deduce the new necessary condition in Theorem 15.

Example 16. For $g(x1,x2,x3,x4,x5,x6)=1+x3+x4+x5+x3x5+x4x6+x2x3x4+x4x5x6+x1x2x3x4x5x6,$$g(x_1,x_2,x_3,x_4,x_5,x_6)=1+x_3+x_4+x_5+x_3x_5+x_4x_6+x_2x_3x_4+x_4x_5x_6+x_1x_2x_3x_4x_5x_6,$ let $f(x0,x1,x2,x3,x4,x5,x6)=x0+g(x1,x2,x3,x4,x5,x6)$$f(x_0,x_1,x_2,x_3,x_4,x_5,x_6)=x_0+g(x_1,x_2,x_3,x_4,x_5,x_6)$ be the FF of a seven-stage NFSR. It can be inspected that $f(x0,x1,x2,x3,x4,x5,x6)$$f(x_0,x_1,x_2,x_3,x_4,x_5,x_6)$ meets all conditions that are listed in Theorem 2. In addition, f does not contain any terms in ${x1x2x3,x3x4x5}$$\{x_1x_2x_3,\,x_{3}x_{4}x_{5}\}$ and contains all terms in ${x1x2x3,x3x4x5}$$\{x_2x_3x_4,\,x_4x_5x_6\}$ with $L(g)=x3+x4+x5$$L(g)=x_3+x_4+x_5$ and $N2(g)=x3x5+x4x6$$N_2(g)=x_3x_5+x_4x_6$. Moreover, computer software verifies that this NFSR cannot produce a dBS.

Conclusions

The main contribution of this paper is that some new necessary conditions for FFs of NFSRs to produce dBSs are presented from the relationship among linear terms, quadratic terms and cubic terms in the FFs of dBSs. The main difference between our proposed necessary conditions and previous necessary conditions lie in the nonlinear terms of the ANF of the FFs of NFSRs. The previous results about the terms of the ANF of the FFs of n-th stage NFSRs focussed on linear terms, quadratic terms and $n−1$$n-1$-th degree term. Our proposed necessary conditions are about quadratic terms and cubic terms in the FFs of dBSs. Besides, some examples are also given to indicate that the known necessary conditions cannot deduce the new proposed necessary conditions in this paper, since the newly obtained necessary conditions are related to the expression of the FFs of NFSRs. By selecting the FFs that satisfied the proposed necessary conditions, it is possible to find the one that generates the dBSs with the help of the computer in a relatively small search range.

Bruijn, de, N. G. (1946). A combinatorial problem, Proc. Kon. Ned. Akad. Wetensch, 49(7), 758-764. Bruijn, de, N. G. (1946). A combinatorial problem, Proc. Kon. Ned. Akad. Wetensch, 49(7), 758-764. Search in Google Scholar

Chan, A.H., Games,R.A., & Key, E.L. (1982). On the complexities of de Bruijn sequences, J. Comb. Theory, Ser. A, 33(3), 233-246. https://doi.org/10.1016/0097-3165(82)90038-3 Chan, A.H., Games, R.A., & Key, E.L. (1982). On the complexities of de Bruijn sequences, J. Comb. Theory, Ser. A, 33(3), 233-246. https://doi.org/10.1016/0097-3165(82)90038-310.1016/0097-3165(82)90038-3 Search in Google Scholar

Golomb, S.W., & Gong,G.. (2005). Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar, Cambridge University Press, New York. https://doi.org/10.1017/CBO9780511546907 Golomb, S.W., & Gong, G.. (2005). Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar, Cambridge University Press, New York. https://doi.org/10.1017/CBO978051154690710.1017/CBO9780511546907 Search in Google Scholar

Golomb, S.W.. (1967). Shift Register Sequences, San Francisco, CA: Holden-Day. https://doi.org/10.1007/11863854_1 Golomb, S.W.. (1967). Shift Register Sequences, San Francisco, CA: Holden-Day. https://doi.org/10.1007/11863854_110.1007/11863854_1 Search in Google Scholar

Menezes, A.J., Oorschot, P., & Vanstone, S.A..(1997). Handbook of Applied Cryptography, Boca Raton, FL: CRC. https://doi.org/10.1201/9781439821916 Menezes, A.J., Oorschot, P., & Vanstone, S.A.. (1997). Handbook of Applied Cryptography, Boca Raton, FL: CRC. https://doi.org/10.1201/978143982191610.1201/9781439821916 Search in Google Scholar

Walker, E.A..(1959). Non-linear recursive sequences, Canadian J. Math, 11(3): 370-378. https://doi.org/10.4153/CJM-1959-037-x Walker, E.A.. (1959). Non-linear recursive sequences, Canadian J. Math, 11(3): 370-378. https://doi.org/10.4153/CJM-1959-037-x10.4153/CJM-1959-037-x Search in Google Scholar

Calik, C., Turan, M.S., & Özbudak, F.(2010). On feedback functions of maximum length nonlinear feedback shift registers, IEICE Trans. Fundamentals, E93-A (6): 1226-1231. https://doi.org/10.1587/transfun.E93.A.1226 Calik, C., Turan, M.S., & Özbudak, F. (2010). On feedback functions of maximum length nonlinear feedback shift registers, IEICE Trans. Fundamentals, E93-A (6): 1226-1231. https://doi.org/10.1587/transfun.E93.A.122610.1587/transfun.E93.A.1226 Search in Google Scholar

Fredricksen, H. (1982). A survy of full length nonlinear shift register cycle algorithms, SIAM Rev., 24(2): 195-221. https://doi.org/10.1137/1024041 Fredricksen, H. (1982). A survy of full length nonlinear shift register cycle algorithms, SIAM Rev., 24(2): 195-221. https://doi.org/10.1137/102404110.1137/1024041 Search in Google Scholar

Wang, Z.X., Qi,W.F., & Chen, H. J. (2014). A new necessary condition for feedback functions of de Bruijn sequences, IEICE Trans. Fundamentals, E97-A(1): 152-156. https://doi.org/10.1587/transfun.E97.A.152 Wang, Z.X., Qi, W.F., & Chen, H. J. (2014). A new necessary condition for feedback functions of de Bruijn sequences, IEICE Trans. Fundamentals, E97-A(1): 152-156. https://doi.org/10.1587/transfun.E97.A.15210.1587/transfun.E97.A.152 Search in Google Scholar

Tang, Z.W., Qi, W.F., & Tian, T. (2015). Necessary Conditions for Characteristic Functions of de Bruijn Sequences, Journal of Information Engineering University, 16(3):263-266. https://doi.org/10.3969/j.issn.1671-0673.2015.03.002 Tang, Z.W., Qi, W.F., & Tian, T. (2015). Necessary Conditions for Characteristic Functions of de Bruijn Sequences, Journal of Information Engineering University, 16(3):263-266. https://doi.org/10.3969/j.issn.1671-0673.2015.03.002 Search in Google Scholar

Tang, Z.W., Qi, W.F., & Tian, T. (2016). On Characteristic Functions of De Bruijn Sequences, Chinese Journal of Electronics, 25 (2): 304-311. https://doi.org/10.1049/cje.2016.03.017 Tang, Z.W., Qi, W.F., & Tian, T. (2016). On Characteristic Functions of De Bruijn Sequences, Chinese Journal of Electronics, 25 (2): 304-311. https://doi.org/10.1049/cje.2016.03.01710.1049/cje.2016.03.017 Search in Google Scholar

Carlet, C. (2010). Boolean Functions for Cryptography and Error-Correcting Codes. In Y. Crama & P. Hammer (Eds.), Boolean Models and Methods in Mathematics, Computer Science, and Engineering (Encyclopedia of Mathematics and its Applications, pp. 257-397). Cambridge: Cambridge University Press. doi:10.1017/CBO9780511780448.011 Carlet, C. (2010). Boolean Functions for Cryptography and Error-Correcting Codes. In Crama Y. & Hammer P. (Eds.), Boolean Models and Methods in Mathematics, Computer Science, and Engineering (Encyclopedia of Mathematics and its Applications, pp. 257-397). Cambridge: Cambridge University Press. doi:10.1017/CBO9780511780448.011