Maximal Length LFSR Feedback Terms
users.ece.cmu.edu
users.ece.cmu.edu
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
There is now a github repository for the software: https://github.com/hayguen/mlpolygen
It is not that simple for larger numbers. The brute force method would require one to check 2^n different values and for each about 2^n steps. That makes 2^2n steps. For n=32 this is about 10^18 steps.
Even assuming O(n^2) multiplication and O(n) prime divisors, checking a single candidate shouldn't take more than O(n^4). I'm sure that in reality you can do much better, probably significantly under O(n^3), e.g. because there are fewer prime factors, using a faster multiplication algorithm, and by reusing intermediate results during the exponentiations.
Factoring 2^n-1 can be done once for a given n in O(2^(n/4)), so it is not the bottleneck.
There are also probably quite a lot of checks that can quickly rule out lots of values without having to give them to the heavy machinery. In the end I expect the total running time to be O(2^n * n^2) or so.