#
Maximum Period NLFSRs

Below we give a complete list of n-bit NLFSRs with the period 2^{n}−1, n < 26, for the following types of feedback functions:
x_{0} ⊕ x_{a} ⊕ x_{b} ⊕ x_{c}· x_{d}

x_{0} ⊕ x_{a} ⊕ x_{b}· x_{c} ⊕ x_{d}· x_{e}

x_{0} ⊕ x_{a} ⊕ x_{b} ⊕ x_{c} ⊕ x_{d} ⊕ x_{e}· x_{f}

x_{0} ⊕ x_{a} ⊕ x_{b} ⊕ x_{c} · x_{d} · x_{e}

where "⊕" is an XOR (addition modulo 2) and " · " is an AND.

The maximum possible period for a n-bit NLFSR is 2^{n}. The NLFSRs listed below do not include all-0 state in their longest cycle of states. They can be extended to have the period 2^{n} by adding to their feedback function a product-term ¬x_{1} · ¬x_{2} · ... · ¬x_{n−1}, where "¬" is a NOT. This increases the circuit complexity of feedback functions, which is undesirable for many applications. For this reason, we prefer to focus on NLFSRs with the period 2^{n}−1.

The results given below were computed by a brute-force simulation which feasible for n < 26 only. FPGAs make possible finding larger
maximum period NLFSRs, as shown in this article.
####
INTRODUCTION TO NLFSRs

The general structure of an n-bit NLFSR is shown in Figure 1.
It consists of n binary storage elements, called *bits* or *stages*, and a feedback function f(x_{0},x_{1},...x_{n−1}). For each i ∈ {0,1,...,n−1 }, the state variable x_{i} represents the value of the bit i. At each clock cycle, the content of the register is shifted one bit right.
The value of the bit n−1 is updated according to the feedback function f.

Figure 1: The general structure of an n-bit NLFSR.

The configuration shown in Figure 1 is usually referred to as the *Fibonacci* configuration. One can also represent an NLFSR in the *Galois* configuration, in which any stage has its own feedback function.

Figure 2 shows an example of a 4-bit NLFSR with the feedback function f = x_{0} ⊕ x_{1} ⊕ x_{2} ⊕ x_{1}· x_{2}.

Figure 2: An example of a 4-bit NLFSR

####
FORMAT OF FEEDBACK FUNCTIONS

In the format we use in the list below, the function f = x_{0} ⊕ x_{1} ⊕ x_{2} ⊕ x_{1}· x_{2} from the example in Figure 2 is represented as 0,1,2,(1,2). Indexes of variables of each product-term are separated by a comma. If a product-term has of more than one variable, we put round brackets around the indexes of its variables.
####
BASIC AND IMPLIED CASES

The state transition graph of an n-bit NLFSR is *branchless*, i.e. consists of pure cycles, if and only if its feedback function is of type
(1) f = x_{0} ⊕ g(x_{1},x_{2},...,x_{n−1})

where the function g(x_{1},x_{2},...,x_{n−1}) does not depend on the variable x_{0}.

Each NLFSR *N* with the feedback function of type (1) has a revserse, a complement, and a reverse-complement NLFSRs which generate sequences which are reverse, complement and reverse-complement of sequences generated by *N*, respectively. In the list below, we show only the basic case. Other three cases are not included.
####
FEEDBACK FUNCTIONS OF n-BIT NLFSRS WITH THE PERIOD 2^{n}−1

- 4-bit NLFSRs
- 5-bit NLFSRs
- 6-bit NLFSRs
- 7-bit NLFSRs
- 8-bit NLFSRs
- 9-bit NLFSRs
- 10-bit NLFSRs
- 11-bit NLFSRs
- 12-bit NLFSRs
- 13-bit NLFSRs
- 14-bit NLFSRs
- 15-bit NLFSRs
- 16-bit NLFSRs
- 17-bit NLFSRs
- 18-bit NLFSRs
- 19-bit NLFSRs
- 20-bit NLFSRs
- 21-bit NLFSRs
- 22-bit NLFSRs
- 23-bit NLFSRs
- 24-bit NLFSRs
- 25-bit NLFSRs

#### REFERENCE

E. Dubrova, "A List of Maximum Period NLFSRs", *Cryptology ePrint Archive*, Report 2012/166, March 2012,
http://eprint.iacr.org/2012/204.
#### CONTACT PERSON

Elena Dubrova

School of Information and Communication Technology

Royal Institute of Technology (KTH)

Stockholm, Sweden

dubrova@kth.se