Cryptology ePrint Archive: Report 2012/166

A List of Maximum Period NLFSRs

Elena Dubrova

Abstract: Non-Linear Feedback Shift Registers (NLFSRs) are a generalization of Linear Feedback Shift Registers (LFSRs) in which a current state is a non-linear function of the previous state. While the theory behind LFSRs is well-understood, many fundamental problems related to NLFSRs remain open. Probably the most important one is finding a systematic procedure for constructing NLFSRs with a guaranteed long period. Available algorithms either consider some special cases, or are applicable to small NLFSRs only. In this paper, we present a complete list of $n$-bit NLFSRs with the period $2^n-1$, $n < 25$, for three different types of feedback functions with algebraic degree two. We hope that the presented experimental data might help analysing feedback functions of maximum-period NLFSRs and finding a supporting theory characterizing them.

Category / Keywords: foundations / NLFSR, maximum length sequence

Date: received 27 Mar 2012

Contact author: dubrova at kth se

Available formats: PDF | BibTeX Citation

Version: 20120330:105756 (All versions of this report)

Discussion forum: Show discussion | Start new discussion