4 ms·

Maximal Length LFSR Feedback Terms

31 points by aww_dang 5y ago

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.

4 ms·

Maximal Length LFSR Feedback Terms

31 points by aww_dang 5y ago

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.