A generic method for investigating nonsingular Galois NFSRs

Abstract

Let n be a positive integer. An n-stage Galois NFSR has n registers and each register is updated by a feedback function. Then a Galois NFSR is called nonsingular if every register generates (strictly) periodic sequences, i.e., no branch points. In this paper, a generic method for investigating nonsingular Galois NFSRs is provided. Two fundamental concepts that are standard Galois NFSRs and the simplified feedback function of a standard Galois NFSR are proposed. Based on the new concepts, a sufficient condition is given for nonsingular Galois NFSRs. In particular, for the class of Galois NFSRs with linear simplified feedback functions, a necessary and sufficient condition is presented.

Appendix

In the following, we prove that $\mathrm {NFSR}( F_{\mathrm {upper}} )$ and $\mathrm {NFSR}( F_{\mathrm {lower}} )$ are inequivalent NFSRs.

Proposition 3

If $k>1$, then $\mathrm {NFSR}( F_{\mathrm {upper}} )$ and $\mathrm {NFSR}( F_{\mathrm {lower}} )$ are inequivalent.

Proof

Suppose NFSR$( F_{\mathrm {upper}} )$ and NFSR($F_{\mathrm {lower}}$) are equivalent. Then there is a permutation $\sigma$ on the set $\{0,1,\ldots , n-1\}$ such that $\sigma ( F_{\mathrm {upper}}) = F_{\mathrm {lower}}$. Let

$$\begin{aligned} \varOmega (F_{\mathrm {upper}})= [i_k+l_k,\ldots , i_k]\parallel [i_{k-1}+l_{k-1},\ldots , i_{k-1}]\parallel \cdots \parallel [i_1+l_1,\ldots , i_1], \end{aligned}$$

and

$$\begin{aligned} \varOmega (F_{\mathrm {lower}})= [j_k+m_k,\ldots , j_k]\parallel [j_{k-1}+m_{k-1},\ldots , j_{k-1}]\parallel \cdots \parallel [j_1+m_1,\ldots , j_1]. \end{aligned}$$

Note that both NFSR$( F_{\mathrm {upper}} )$ and NFSR($F_{\mathrm {lower}}$) are standard NFSRs, and so $\sigma$ only permutes the order of $[i_1+l_1,\ldots , i_1] ,\ldots , [i_k+l_k,\ldots , i_k]$. Then for $1\le u\le k$ we have

$$\begin{aligned} (\sigma (i_u),\sigma (i_u+l_u)) \in \{(j_1,j_1+m_1),(j_2,j_2+m_2),\ldots , (j_k,j_k+m_k)\}. \end{aligned}$$

Since the entry $a_{u,v}$ in $\mathcal {M}(F_{\mathrm {upper}}) = (a_{u,v})_{k\times k}$ is the coefficient of $x_{i_v}$ in $f_{i_u+l_u}$, it follows that there is a $k\times k$ permutation matrix A such that

$$\begin{aligned} \mathcal {M}(F_{\mathrm {lower}}) = A \cdot \sigma (\mathcal {M}(F_{\mathrm {upper}})) \cdot A^{T}. \end{aligned}$$

(10)

Since

$$\begin{aligned} A\cdot \left( \begin{array}{cccc} 1 &{} 0 &{} \cdots &{} 0 \\ 0 &{} 1 &{} \cdots &{} 0 \\ \vdots &{} \vdots &{} \vdots &{} \vdots \\ 0 &{} 0 &{} \cdots &{} 1\\ \end{array} \right) \cdot A^{T} = \left( \begin{array}{cccc} 1 &{} 0 &{} \cdots &{} 0 \\ 0 &{} 1 &{} \cdots &{} 0 \\ \vdots &{} \vdots &{} \vdots &{} \vdots \\ 0 &{} 0 &{} \cdots &{} 1\\ \end{array} \right) , \end{aligned}$$

we have

$$\begin{aligned} A\cdot \sigma (\mathcal {M}(F_{\mathrm {upper}})) \cdot A^{T} = \left( \begin{array}{cccc} 1 &{} \cdots &{} *&{} *\\ *&{} 1 &{} \cdots &{} *\\ \vdots &{} \vdots &{} \vdots &{} \vdots \\ *&{} *&{} \cdots &{} 1\\ \end{array} \right) , \end{aligned}$$

i.e., multiplying A on the left and $A^{T}$ on the right of $\sigma (\mathcal {M}(F_{\mathrm {upper}}))$ will not change the main diagonal. It can be seen that when $k>1$, the first entry in $\mathcal {M}(F_{\mathrm {lower}})$ is 0 while the first entry in $A\cdot \sigma (\mathcal {M}(F_{\mathrm {upper}})) \cdot A^{T}$ is 1, a contradiction to (10). Hence, NFSR$( F_{\mathrm {upper}} )$ and NFSR($F_{\mathrm {lower}}$) are inequivalent when $k>1$. $\square$