3 ms·

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 solv

by hvenev 5y ago

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 https://oeis.org/A011260

fjfaase 5y ago
The link for #A011260 is https://oeis.org/A011260 https://oeis.org/A011260 There is now a github repository for the software: https://github.com/hayguen/mlpolygen 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.
- hvenev 5y ago
  Evaluating 2^k steps takes O(k) multiplications when done using a fast exponentiation algorithm. 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.

by hvenev 5y ago

fjfaase 5y ago

The link for #A011260 is https://oeis.org/A011260 https://oeis.org/A011260 There is now a github repository for the software: https://github.com/hayguen/mlpolygen 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.

hvenev 5y ago
Evaluating 2^k steps takes O(k) multiplications when done using a fast exponentiation algorithm. 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.