[HN Gopher] Maximal Length LFSR Feedback Terms
       ___________________________________________________________________
        
       Maximal Length LFSR Feedback Terms
        
       Author : aww_dang
       Score  : 26 points
       Date   : 2022-02-19 11:51 UTC (1 days ago)
        
 (HTM) web link (users.ece.cmu.edu)
 (TXT) w3m dump (users.ece.cmu.edu)
        
       | hvenev wrote:
       | 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
        
         | fjfaase wrote:
         | The link for #A011260 is 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.
        
           | hvenev wrote:
           | 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.
        
       ___________________________________________________________________
       (page generated 2022-02-20 23:01 UTC)