Let's suppose I have an [LFSR](https://en.wikipedia.org/wiki/Linear-feedback_shift_register) 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](https://www.embeddedrelated.com/showarticle/1093.php) 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](https://www.embeddedrelated.com/showarticle/1099.php), 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)$.



Computing the decimation ratio between two m-sequences
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](https://pari.math.u-bordeaux.fr/) 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.


