# What are the methods to construct a primitive binary nonlinear feedback shift register (NLFSR)?

Given a binary shift register of $n$ bits, a primitive binary nonlinear feedback shift register will generate a sequence with a period of $2^n - 1$.

While I am unable to find a paper which directly describes the methods, the paper A List of Maximum Period NLFSRs has just came up on eprint, which lists all NLFRSs with a period of $2^n - 1$, for $n < 25$.

Does anyone have links to papers describing the construction methods for such primitive binary nonlinear feedback shift registers?

• The Motorola website has application notes for older pseudo-digital chipsets (CVDSM, etc). Look for shift registers and drill down from there. Opencores dot org is also an excellent resource. AFAIK, they are not secure because of LSB change bias which is relatively predictable (the lesser significant bits have more change bias in the long run). – Iceberg Hotspot Apr 11 '12 at 4:54

Update: A general method is given by Elena Dubrova: A Scalable Method for Constructing Galois NLFSRs with Period $2^n-1$ using Cross-Join Pairs, in IEEE Transactions on Information Theory, Volume 59, Issue 1 (alternate link). It gives an extensive bibliography of earlier constructs.

These constructions reorder a small number of fragments of the output sequence of a maximum-length LFSR. It does not achieve (or aim at) cryptographic security: it remains trivial to reconstruct the state of the generator from its output, from any unbroken fragment of at least $n$ bits. With slightly more bits, it is possible even if details (like $n$ and the polynomial) are unknown, using an appropriate variant of the Berlekamp-Massey algorithm.

Other than tweaking a LFSR to reorder fragments of its output sequence, I know no general method to construct Non-Linear Feeback Shift Registers with $n$ bits and period $2^n-1$, beside basically trying one by simulating the NLFSR for that number of steps, with cost $O(2^n)$ when done naively.

Large speedups are possible depending on the construct; in particular, if it is possible to explicitly compute the states that could reach the original state within $s$ steps, and performs $s$ steps as fast as one step, we can save a factor of $s$. But still the cost of establishing that a NLFSR with $n$ bits is near-maximal-period would be, it seems, at least $O(2^{n/2})$ steps with $O(2^{n/2})$ memory. However it is clearly easy to go much further that $n=25$ bits. Caveat: this is out of my head, I have no reference to quote.

In practice, it seems open cryptography seldom use maximal-length NLFSR; they could however make some sense in a cascaded construct, similar to the Alternating Step Generator or Shrinking Generator.

Also: There is simple method to construct a NLFSR with period $2^n$ using a binary shift register of $n$ bits. We start from a maximal-length LFSR with period $2^n-1$ constructed from a degree $n$ primitive polynomial over $GF(2)$, and tweak it into a binary De Bruijn sequence by inserting a single $0$ bit at the point in the sequence where $n-1$ consecutive $0$ occur. For a LFSR implemented as a shift register with a feedback term the XOR of some state bits, that's simply adding an additional XOR term with the NOR of the $n-1$ bits in the shift register that are closest to the feedback term. As a bonus, we can now start the generator in any state, including all-zero. See this related answer for details. Of course, that's not cryptographically secure.