# 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

1
Try googling maximum-length NLFSR – fgrieu Mar 19 '12 at 17:42

1
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
– Bluemilk Mar 30 '12 at 15:20
show 2 more comments

## 2 Answers

As far as I know, there is 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, probably for that very lack of known method to study their period; they could however make some sense in a cascaded construct, similar to the Alternating Step Generator or Shrinking Generator.

-

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).
Hope that helps, Iceberg

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 14, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9291658997535706, "perplexity_flag": "middle"}