Shifting an LFSR loop in O(1) time?

Question

I'm looking for a way to mathematically combine two concepts: LFSRs, and Barrel Shifters

I'm looking for a way, in O(1) time, to shift an LFSR loop a given number of shifts.

What I'm hoping to find is a simple process where I have the current state of the LFSR and the number of times I want to shift from that state as parameters to a quick/easy process.

At first I just thought about looking at all the taps, then moving the taps over by 1 and looking at them again, finding the shift in bit each time and appending it onto the end but of course this isn't O(1) and it gets complicated if I want to shift so many times that a tap would "slide off" the original LFSR state.

I may be in the wrong place to ask this because I'm looking for a way to do this programmatically. Although any incite into how it's possible (or why it's impossible) would be very helpful.

Answer 1

The successive contents of a (binary) maximal-length linear feedback shift register with $n$ stages can be interpreted as the elements $\ldots, \alpha^{i-1}, \alpha^i, \alpha^{i+1}, \ldots,$ of $\mathbb F_{2^n}$ (where $\alpha$ is a primitive element in the field) expressed in the dual-polynomial basis (see the answers and comments on this question). So what you are asking is,

Given the current state $\alpha^i$ and an integer $j$, compute the state $\alpha^{i+j}$ as quickly as possible (preferably in $O(1)$ time).

This would require either

• exponentiation (compute $\alpha^j$) followed by multiplication (to find $\alpha^i \times \alpha^j$)

or

• a discrete logarithm computation (find $i = \log_{\alpha}(\alpha^i)$ followed by addition ($i+j$) and exponentiation.

This fleshes out @YuvalFilmus's hint that a simple method may not exist. Of course, if $n$ is not too large, and the set of values of $j$ that you are interested in is not too large, table look-up would be the way to solve the problem instead of barrel shifters. If $j$ can be only two or three values, you can implement the transformation $\alpha^i \to \alpha^{i+j}$ using Exclusive-OR trees with feedback going not just to the last stage of the LFSR but to several stages.