3
$\begingroup$

Let's suppose I have an LFSR that generates an m-sequence $y_1[k]$ --- in other words, the LFSR has $N$ bits and $y_1[k]$ has period $m=2^N - 1$.

Now suppose I know someone has decimated this and taken every $j$th element, so $y_2[k] = y_1[jk+b]$. And I know the $y_2[k]$ but the values of $j$ and $b$ are unknown.

Is there any efficient way to compute the decimation ratio $j$ without testing all possible values of $j$?

(Note 1: if $b$ is unknown then there are $N$ possible solutions for $j$ because $2j, 4j, 8j, \ldots\, j^{2^{N-1}}$ can have sequences generated by LFSRs with the same coefficients, differing only by a time shift. I have no idea if the problem is easier to solve for known $b$.)

(Note 2: This smells vaguely like a discrete logarithm problem but I cannot figure out how to restate it as such. I will be satisfied if I can obtain an equivalent discrete logarithm problem, because the values of $N$ that I deal with are small enough that I can use established techniques like Pollard's rho and kangaroo algorithms to compute the value of $j$.)


There are several equivalent ways of stating this problem (I posted one on https://math.stackexchange.com/questions/2480132/determining-decimation-ratio-given-characteristic-polynomials-of-quotient-rings):

  • $y_1[k] = \operatorname{Tr}_{F_1}(w_1x^k)$ where $F_1 = GF(2)[x]/p_1(x)$ and similarly for $y_2[k], F_2, w_2, p_2(x)$; the traces are related (because of the decimation ratio $j$) by $\operatorname{Tr}_{F_1}(w_1x^{jk+b}) = \operatorname{Tr}_{F_2}(w_2x^k)$; the coefficients of $p_1(x)$ are the LFSR coefficients; $p_2(x)$ can be determined from the Berlekamp-Massey algorithm, and $w_1$ and $w_2$ can be determined from state recovery methods by running the LFSR backwards (I have a blog article in progress on this but it's unfinished and not a quick thing to summarize, sorry)

  • $p_1(x)$ is the minimal polynomial of $x$ in $F_1 = GF(2)[x]/p_1(x)$; $p_2(x)$ is the minimal polynomial of $x^j$ in $F_1$ and $p_2(x)$ is also the minimal polynomial of $x$ in $F_2 = GF(2)[x]/p_2(x)$; given $p_1(x)$ and $p_2(x)$, what is $j$?


Example:

  • $p_1(x) = x^9 + x^4 + 1$
  • $y_1[0..18] = [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1]$
  • $j = 107, b = 80$
  • $y_2[0..18] = [1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0]$

We can use Berlekamp-Massey on the $y_2$ values to determine $p_2(x) = x^9+x^7+x^5+x+1$, and state recovery techniques to determine that $y_2[k] = HB(v_2x^k)$ with $v_2 = x^8 + x^6 + x^5 + x^4 + x^3$ (equivalently the LFSR has initial state 101111000), where $HB(u)$ is the high bit = coefficient of $x^8$.

But I'm stuck on how to get from there to $j=107$ or other members of its cyclotomic coset $\{107, 214, 428, 345, 179, 358, 205, 410, 309\}$, aside from checking every value of $j$ --- or at least, the smallest coset representative of every value of $j$, and then using Berlekamp-Massey until I get a match of $p_2(x)$.

$\endgroup$
2
$\begingroup$

In general, $p_2$ has $x^j$ as a zero in $F_1$. In other words, $p_1(x)$ divides $p_2(x^j)$ over $\mathrm{GF}(2)$.

To find $j$ from the given $p_1$ and $p_2$, one can factor $p_2(y)$ in $F_1[y]$, and for every zero $y_0\in F_1$ of $p_2(y)$, find the discrete log of $y_0$ base $x$ in $F_1$.

Here is a sample PARI/GP code that recovers values of $j$ in the given example:

? X = ffgen((x^9+x^4+1)*Mod(1,2));  \\ x as an element of F1
? lf = select(t->poldegree(t,x)==1, factorff(x^9+x^7+x^5+x+1,2,y^9+y^4+1)[,1] ); \\ linear factors of p(y)
? for(i=1,#lf, z = lift( -polcoeff(lf[i],0)/polcoeff(lf[i],1) ); print( fflog(subst(z,y,X),X) ) )
214
345
309
358
428
205
410
179
107

Notice that $p_1$ and $p_2$ alone do not uniquely define $j$ (e.g., in the example above there is an extraneous value $179$), but together with initial terms of the decimated sequence they do.

$\endgroup$
  • $\begingroup$ dumb question, what's $F_1$? is that the infinite set of integers? I'm familiar with the notation $F_{q^n}$ for finite fields. $\endgroup$ – Jason S Nov 16 '17 at 22:16
  • 2
    $\begingroup$ @JasonS: You defined $F_1$ in your question. $\endgroup$ – Max Alekseyev Nov 16 '17 at 22:20
  • $\begingroup$ Everything else looks promising -- I have to check my mental model of all this to make sure I understand all the pieces but I'm familiar with polynomial factoring techniques so I think I can translate this to the Python code I work with. Does it work with any value of $j$, or just the ones that are relatively prime to $2^N-1$ where $p_2(x)$ is a primitive polynomial? $\endgroup$ – Jason S Nov 16 '17 at 22:21
  • $\begingroup$ OH -- okay, oops. Haha. $\endgroup$ – Jason S Nov 16 '17 at 22:22
  • 1
    $\begingroup$ After some work to understand and implement, Cantor-Zassenhaus worked nicely for me. This article helped (ignore the title, it discusses $GF(2)$ also). Thanks for the suggestion! $\endgroup$ – Jason S Nov 18 '17 at 14:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.