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.