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