Computing the decimation ratio between two m-sequences

Question

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)$.

Answer 1

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.