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
I finally asked this question on mathoverflow.net and got a very helpful answer.
The short answer is to follow essentially the following procedure:
Find any root $y_1 \in F_1$ of $p_2(y)$ in the polynomial ring $F_1[y]$ --- these are the polynomials $p(y)$ which have coefficients that are elements in $F_1$ and are themselves polynomials.
Take the discrete logarithm to determine $j$ such that $x^j = y_1$
- Any decimation ratio in the cyclotomic coset of $j$ is a valid decimation ratio.
I've written up a longer description in my blog post which includes the use of a factoring method that partitions $p(y)$ as $p(y) = \gcd(p(y),S(x^ky))\gcd(p(y),S(x^ky)-1)$ where $S(u) = u + u^2 + u^4 + u^8 + \ldots + u^{2^N-1}$, which is mentioned in Lidl + Niederreiter and also in http://blog.fkraiem.org/2013/12/01/polynomial-factorisation-over-finite-fields-part-3-final-splitting-cantor-zassenhaus-in-odd-characteristic/.
No comments:
Post a Comment