Paper 2014/536

A Survey and New Results on the Decomposition of an NFSR into a Cascade Connection of Two Smaller NFSRs

Tian Tian and Jia-Min Zhang and Chen-Dong Ye and Wen-Feng Qi

Abstract

Nonlinear feedback shift registers (NFSRs) are an important building block for stream ciphers. Given a cascade connection of two NFSRs, say NFSR$(f,g)$, it has been known for decades how to solve the characteristic function of the NFSR which is equivalent to NFSR$(f,g)$. However, the converse problem of decomposing an NFSR into a cascade connection of two smaller NFSRs is not completely solved, and only a special case has been studied recently. In this paper, a complete and feasible solution to the problem is given.