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