Is there a feasible way to compute the number of steps between two sequences generated by a linear feedback-shift register?

Question

Consider a full-period LSFR with a feedback polynomial of degree n. In the cyclic sequence generated by the LSFR, each n-bit sequence appears exactly once. Given two n-bit sequences, one can define the distance as the number of application of the recursion rule that are needed to move from the first to the second sequence (note that this will not be symmetric). The distance can obviously be computed by iterating the LSFR until the second sequence is met, but this is unfeasible unless n is very small.

Is there a better (say, $O(n)$ or $O(n^2)$ instead of $O(2^n)$) way?

Answer 1

It just occurred to me that the following procedure might work. Assume $P$ is the feedback polynomial.

1) Use the two sequences to build a feedback polynomial $P'$ that will move in one step from the first one to the second one. There is always such a polynomial.

2) Compute $d$ such that $x^d = P' \mod P$ (this has a solution because $P$ is primitive).

Since $P$ is the characteristic polynomial of the companion matrix, the matrix satisfies $P$ and the discrete logarithm modulo $P$ gives the exponent of the transition matrix moving from the first sequence to the second one.

From what I see, recent progress in computing the discrete logarithm on field of small characteristic might make this feasible for n in the thousands, but I haven't been able to locate specific software, so any suggestion is appreciated.

Answer 2

Let $N=2^n-1$ and $m=\lceil N\rceil.$ The baby step giant step Pohlig Hellman algorithm works by generating the lists

$$A=\{1,x^m,x^{2m},\ldots, x^{m(m-1)}\}$$ and $$B=\{1,x,x^{2},\ldots, x^{m-1}\}$$ and given $y=x^b$ with unknown $b$ computes $y B$, finds its intersection with $A$ and solves $$ y x^i=x^{b+i}=x^{jm} $$ for $b$, where $i,j$ are determined by the colliding elements uniquely.

It is $O(\sqrt{N})$ in time and memory complexity and can be used here.

The new discrete log algorithms due to Joux and others mentioned might work better, being pseudopolynomial.

Edit: If you're allowed precomputation, a binary tree (or other search structure) can be built where the leaf nodes have the value of $b$ corresponding to the binary path label from the root which represents the LFSR state. The query complexity becomes $O(\log N)$ but the huge table is a problem.