According to "The Art of Electronics" the criterion for maximal length
is that the polynomial
1 + x^n + x^m
must be polynomial and prime over the Galois field, where m is the
length of the shift register in bits, and n is the tap number.
I tried to make sense of a similar assertion when looking at error-
detecting and error-correcting codes back in 1970, and didn't get
anywhere at all. Mathematicians who study the algebra of finite fields
seem to do better.
So the algorithm is to try a set of feedback bits and see if it meets
the requirement. There IS a maximal length sequence for all shift
register lengths; in fact, there are huge numbers of them for long
shift registers. It's relatively quite easy to determine the number
of maximal length polynomials of a given order. Finding them for long
registers--high orders--is not necessarily easy (or fast). However,
once you've found one, you can generate lots of others easily. For
some cases, there are not any feedback schemes using only two values
xored together; for some you need to modulo-2 sum four bits, minimum.
(It's relatively easy to show that you always need an even number of
bits fed back, and it should be obvious that you always must include
the last bit.) You can find lists of feedback that works--of maximal
length polynomials. The ap notes on the Xilinx web site has one such
list, up to some pretty long sequences. Finding a maximal length
polynomial for some arbitrary but high order (hundreds or even
thousands) would be a good task for the idle time of processors
distributed around the world, connected by the internet. That's been
used to find some related numbers...numbers such that 2^n-1 is prime.
How those are related to maximal length shift registers is left for
another day...
Cheers,
Tom