I have an LFSR, essentially $x^k \bmod p(x)$ for some characteristic primitive polynomial of degree $N$ with coefficients in $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.)
  • $\begingroup$ Could you clarify the second bullet point? Do you mean you want to find a $k$ in the interval for which the polynomial has the given form? Do you know whether there is such a $k$ to begin with? Also, what do you mean by the interval being small? If it's small enough, you might just compute the relevant $x^k$ and see if they are of the required form. $\endgroup$ – Felipe Voloch Nov 29 '17 at 0:03
  • $\begingroup$ Yes on the first question, and yes, I know there is such a $k$. As far as numbers, consider $N=48$ with $k_2 - k_1$ in the $10^3 - 10^6$ range, which is small enough to enumerate every value but that is too time consuming for practical purposes. The regular discrete logarithm for $N=48$ is very fast to solve with Silver-Pohlig-Hellman if you have table lookup for each of the subgroups. $\endgroup$ – Jason S Nov 29 '17 at 4:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.