On the Uniqueness of Decomposition of a NFSRinto a Cascade Connection of Smaller NFSRs

The Nonlinear Feedback Shift Register.(NFSR) is one of hot topics of stream cipher in recent studies. The uniqueness of a NFSR assuming to be decomposed into a cascade connection of smaller NFSRs is discussed in this paper. Firstly, the decomposition of Linear Feedback Shift Register.(LFSR) is equivalent to the decomposition of univariate polynomials over the finite field of two elements F2, thus it is unique. Secondly, for the case that a NFSR can be decomposed into a cascade connection of a NFSR into a LFSR, a necessary and sufficient condition is offered for a NFSR to have such a decomposition. Based on this condition, it is indicated that during all such decompositions, the largest LFSR is unique. However, the construction of counterexamples in a class shows that, for the general cases, the decomposition of a NFSR into a cascade connection of smaller NFSRs is not unique.