# 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?

-
What would be the definition of a primitive NLFSR? Aren't you looking for something more like a maximal-length NLFSR? –  fgrieu Mar 19 '12 at 11:16
Yes, that would be another way of describing it. Thanks for clarifying. –  Bluemilk Mar 19 '12 at 15:45
Try googling maximum-length NLFSR –  fgrieu Mar 19 '12 at 17:42
Please update and expand the question with a common terminology (maximal-length), or a definition of primitive in the context; references to the constructs that you considered; and explanation on why they are not fit, or more generally your goal. –  fgrieu Mar 20 '12 at 6:41
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, a paper has just came up on eprint which lists all NLFRSs with a period of 2^(n) - 1, for n < 25. The paper can be found here: eprint.iacr.org/2012/166 –  Bluemilk Mar 30 '12 at 15:20

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).

-

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 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.

-