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.

somethingeven though I know nothing of the field. I do know that linear-logic feels like the wrong tag (there is a field of mathematical logic called linear logic which has restrictions on the usual structural rules of sequent calculus). $\endgroup$ – Todd Trimble♦ Nov 22 '10 at 17:27