LFSR period and order I am doing some work on LFSR (linear feedback shift register). If I have a LFSR of order $m$ (so, the next value $x_k$ depends on the $m$ previous values with certain coefficients $c_i$ vor $i \in \{0,\dots,m-1\}$. Now I am trying to understand what it means for the order if a LFSR is of period $2^m-1$. What I mean is, is it possible for a LFSR to be of order $m-1$ with period $2^m-1$? I am not sure about that fact.
There was also stated that if we start with a certain start sequence of length $m$, then we always get that sequence of period $2^m-1$. I think that it will only be shifted, but intuitively I don't understand why this holds. Can someone help me out with this?
 A: The order or the length of the LFSR is the number of states that it can hold.
Now consider that each state of the LFSR of length $m$ can hold 1 bit - yes one can design an LFSR that can hold large values - then there are possible $2^m$ possible states. An LFSR with the feedback polynomial will jump from one state to another. Since there are $2^m$ states it will start to repeat itself once a previous state is visited again. Since LFSR's are deterministic, they will repeat themselves, there you can find the period. Actually, the period can be determined with the characteristic polynomial.
Another way of seeing this; if you represent the states as an integer then all values from $0$ to $2^{m}-1$ can be a state of the LFSR, no more than this. This again will imply the upper bound on the period.
Why the $2^m-1$? An LFSR with an all-zero state will always produce the all-zero sequence. As a result of this, a maximal period LFSR can visit all states, except the all-zero state, if not started from all-zero state. Then the period will be $2^m-1$
If you want to learn more about LFSRs, see;

*

*Rainer Rueppel's book (Thesis) (Analysis and Design of Stream Ciphers (Communications and Control Engineering Series)

*Solomon W Golomb's book Shift Register Sequences: Secure And Limited-access Code Generators, Efficiency Code Generators, Prescribed Property Generators, Mathematical Models (Third Revised Edition), is advised.

