Judging by the fact that all external links on this page appear to be dead, this must be quite old.

Also, isn't generating/enumerating maximal length LFSR solved? AFAIK the maximal length is known to always be 2^n-1 for n bits.

It should be relatively straightforward to check if a given polynomial has the maximum cycle length. All you need to do is make sure that it repeats after 2^n-1 steps but not after any of its divisors. Evaluation can be done using something similar to double-and-add, so assuming 2^n-1 is factored the check should run in poly(n) time.

A (not entirely trivial to compute) formula for the number of max-length terms is also known: https://oeis.org/A011260