I have an LFSR, essentially $x^k \bmod p(x)$ for some characteristic primitive polynomial of degree $N$ with coefficients in $\mathrm{GF}(2)$, as outlined in Clark and Weng's article: it has a period $2^N - 1$ (= order of the associated finite field) that is a "smooth" integer (prime factors are small), e.g. $N=48$ (largest factor of 673) or $N=60$ (largest factor of 1321).
I know how to compute discrete logarithms using Silver-Pohlig-Hellmann given a completely determined polynomial, so if you told me, Hey you! I have $$x^{23} + x^{16} + x ^ {14} + 1 \equiv x^k \pmod {p(x)}$$ so what's $k$ ? Then I could tell you by following the algorithm.
But what if I don't know all of the coefficients, e.g. all I know is
$$a_{31}x^{31} + a_{30}x^{30} + a_{29}x^{29} + x^{23} + a_{20}x^{20} + x^{16} + x ^ {14} + a_2x^2 + 1 \equiv x^k \pmod {p(x)}$$
and I don't know the five unknown $a_j$'s (so $k$ has $2^5 = 32$ principal solutions). Aside from running through each of the possibilities, is there a way to figure out $k$ from one of them (e.g. set the unknown $a_j$ to zero, then take discrete logarithm), and then determine the rest?
I am interested in a couple of variants of this problem, in case there are no general solutions but there are some specific solutions:
- the unknown $a_j$ are leading coefficients
- the value of $k$ is confined to an interval, e.g. $k \in [k_1, k_2]$ where $k_2 - k_1$ is large in absolute terms, but small compared to $2^N-1$. (Similar to the situation in Pollard's kangaroo algorithm but I don't see how that can be of use here.)