2
$\begingroup$

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.)
$\endgroup$
4
  • $\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$ Nov 29, 2017 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, 2017 at 4:54
  • 1
    $\begingroup$ The link in the paper no longer works - but here is a working link: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.118 (with citeseerx instead of citeseer in the URL). The paper in question is "Douglas W. Clark, Lih-jyh Weng : Maximal and Near-Maximal Shift Register Sequences: Efficient Event Counters and Easy Discrete Logarithms". $\endgroup$ Mar 4, 2023 at 8:35
  • $\begingroup$ thanks -- fixed! $\endgroup$
    – Jason S
    Mar 4, 2023 at 17:58

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.