I know it's possible with work backwards from the output bits of an LFSR to determine its feedback polynomial in a O(n) fashion. I'm also curious if, given an LFSR state and polynomial, is it possible to quickly work out how far the LFSR state is from a given epoch state (eg: the all-ones state). The only sure-fire method I know of is to run the LFSR forwards/backwards until the state is the epoch state and keep track with a counter.
Edit: thinking about this more, this would be equivalent to solving $S = M^NE$ quickly $N$, where $S$ is your current state, $E$ is the epoch state and $M$ is the companion matrix of the LFSR. Anyone have a fast solution to the discrete logarithm problem in the ring of $KxK$ $GF(2)$ matrices?