Shifting an LFSR loop in O(1) time? 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.
 A: 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.
