Obviously you can exhaustively check that it lands on every state except the zero state, but for large LFSRs, 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.

(I can't create the tag LFSR, somebody want to edit that tag in for me?)

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). – Todd Trimble♦ Nov 22 '10 at 17:27