How are taps proven to work for LFSRs?

Question

Obviously, you can exhaustively check that it lands on every state except the zero state, but for large linear feedback shift registers (LFSR), this quickly becomes infeasible.

Wikipedia states the following on its LFSR page:

• The LFSR will only be maximum-length if the number of taps is even; just 2 or 4 taps can suffice even for extremely long sequences.
• The set of taps must be relatively prime, and share no common divisor to all taps.
• There can be more than one maximum-length tap sequence for a given LFSR length
• Once one maximum-length tap sequence has been found, another automatically follows. If the tap sequence, in an n-bit LFSR, is [n, A, B, C, 0], where the 0 corresponds to the x0 = 1 term, then the corresponding 'mirror' sequence is [n, n − C, n − B, n − A, 0]. So the tap sequence [32, 7, 3, 2, 0] has as its counterpart [32, 30, 29, 25, 0]. Both give a maximum-length sequence.

I don't believe that this is a complete set of requirements for taps. Nevertheless this doesn't touch the subject of proving the taps create a maximum-length LFSR.

I know there are tables out there, but I am interested specifically in finding and proving that a set of taps create a maximum-length LFSR.

Answer 1

This wikipedia page is not particularly well-written and the list you quote is just a list of observations, confusingly phrased. Some of them include necessary conditions for the LFSR to be maximal but not a sufficient one.

Everything is best phrased in terms of the characteristic polynomial $f=1+x^{n_1}+\cdots+x^{n_r}$, where $n_1 < \cdots <n_r $ are the taps and $n=n_r$. This polynomial is considered over the field of two elements (i.e. modulo 2). The condition on the polynomial for the LFSR to be maximal is that $f$ is (irreducible and) primitive, i.e. a root of $f$ in the field of $2^n$ elements generates its multiplicative group. Now for the four bulleted statements;

First, $r$ has to be even, for otherwise $(x+1)$ divides $f$. It is a conjecture that for every $n$ there is a primitive polynomial with $r=2$ or $4$.

If $k>1$ divides all the $n_i$, then $f(x)=g(x^k)$, $g$ has degree $n/k$ and a root of $g$ will have order at most $2^{n/k}-1$. Since the $k$-th power of a root of $f$ is a root of $g$, the order of a root of will be at most $k(2^{n/k}-1) < 2^n-1$.

There can be more than one primitive polynomial, in fact there are $\phi(2^n-1)/n$ of them.

Finally, if $f$ is primitive then clearly so is $x^nf(1/x)$ which gives the fourth statement.

To actually check if $f$ is primitive, computing in $\mathbb{F}_2[x]/(f(x))$, you need to show that $x^{(2^n-1)/d}\ne 1$ for all non-trivial factors $d$ of $2^n-1$. If you can factor $2^n-1$ this is a reasonably simple task.