6
$\begingroup$

I know it's possible with work backwards from the output bits of an LFSR to determine its feedback polynomial in a O(n) fashion. I'm also curious if, given an LFSR state and polynomial, is it possible to quickly work out how far the LFSR state is from a given epoch state (eg: the all-ones state). The only sure-fire method I know of is to run the LFSR forwards/backwards until the state is the epoch state and keep track with a counter.

Edit: thinking about this more, this would be equivalent to solving $S = M^NE$ quickly $N$, where $S$ is your current state, $E$ is the epoch state and $M$ is the companion matrix of the LFSR. Anyone have a fast solution to the discrete logarithm problem in the ring of $KxK$ $GF(2)$ matrices?

Improve this question
$\endgroup$
6
  • $\begingroup$ If $P$ is the generating polynomial, $F$ the final state, and $G$ the initial state, you are asking is we can find a $j$ such that $F=G\cdot x^j\mod P$, faster than with effort $\mathcal O(j)$ or $\mathcal O(2^n)$. Looks like a discrete logarithm problem to me, and the answer would thus be yes, we can do better than $\mathcal O(2^n)$. $\endgroup$
    – fgrieu-onstrike ♦
    Jul 2, 2014 at 18:04
  • $\begingroup$ Ack you responded before I submitted my edit, I promise I didn't crib from you. So you're saying there's no fast way correct? $\endgroup$
    – gct
    Jul 2, 2014 at 18:08
  • $\begingroup$ What's "j that pays" mean? $\endgroup$
    – gct
    Jul 2, 2014 at 18:21
  • 1
    $\begingroup$ Update: We can do much better than $\mathcal O(2^n)$, where $n$ is the degree of $P$, but I do not know how much better, or starting with how many steps of the generator it is possible to beat the trivial method, or exactly what method is best.$\;$ I see at least a simple method with cost $\mathcal O(2^{n/2})$ and about $n\cdot2^{n/2}$ bits of memory: starting from the final state, we step $2^{n/2}$ times and store the states. Then starting from the initial state we repeatedly advance by $2^{n/2}$ steps using a precomputed matrix, and search that state in our memory. $\endgroup$
    – fgrieu-onstrike ♦
    Jul 2, 2014 at 19:57
  • $\begingroup$ I thought on it a bit and you can actually reduce it as far as you want by pre-computing a hash table that maps state -> N. You can decimate the field by however much you want at a cost of having to seek at most that far to find the element in the hash table. $\endgroup$
    – gct
    Jul 2, 2014 at 21:29

2 Answers 2

Reset to default
7
$\begingroup$

Well, one way to look at this is to notice that, if the feedback polynomial is prime, then the result of starting with state $E$, and then stepping the LFSR forward $N$ steps is the value $2^N \cdot E$, where we do the computation in $GF(2^K)$, using the polynomial representation (with the feedback polynomial being the polynomial). In addition, I believe that if the feedback polynomial is not prime, then it is possible to factor that polynomial into its primes, solve the equivalent solution modulo each prime factor, and then recombine them.

So, the solving the problem of finding $N$ is equivalent to solving $S = 2^N \cdot E$ in $GF(2^K)$, or in other words, $S/E = 2^N$; that is, this problem can be reduced to solving a discrete log problem in $GF(2^K)$.

What does that rewording of the problem buy us? Well, it turns out that there are recent results in this area; this paper shows us how this problem can be solved in "quasi-polynomial" time (by which they mean $K^{O(\log K)}$; technically supra-polynomial, but just barely); that paper tells us how to do discrete logs quickly over fields of small characteristic, and a characteristic of 2 is as small as it gets.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Very interesting, thanks. I hadn't though about taking the entire LFSR state as an element in a larger field, but that makes perfect sense. $\endgroup$
    – gct
    Jul 2, 2014 at 21:26
  • $\begingroup$ I still wonder what the best (known) algorithm is (it seems possible that an algorithm for characteristic 2 beats a general algorithm for small characteristics); its runtime and memory requirements; and how much its runtime depends on $P$ (is it harder for a random primitive $P$ than e.g. the primitive $P$ with lowest possible $P(2)$? $\endgroup$
    – fgrieu-onstrike ♦
    Jul 3, 2014 at 11:55
  • $\begingroup$ @fgrieu: the $GF(2^k)$ argument can be used to address the later question; for two different polynomial representations of $GF(2^k)$, there is a linear mapping that preserves the field structure. Hence, we can use that mapping to map from the "hard" representation to the "easy" one, and solve it there. Now, the constant "2" in the hard representation will (probably) map to some other constant; if the easy solution depends on the base 2, we just solve two discrete logs in the easy representation. $\endgroup$
    – poncho
    Jul 3, 2014 at 14:33
  • $\begingroup$ If the primitive $P$ of degree $k$ of the generator is not sparse or otherwise unfit, I trust you that we can massage $S/E\equiv x^N\pmod P$ into $A\equiv B^N\pmod Q$, where $Q$ is any primitive polynomial we see fit, and polynomials $A$ and $B$ somehow follow (I fail to tell exactly how, though). We can then solve $A\equiv x^{N_A}\pmod Q$ and $B\equiv x^{N_B}\pmod Q$, and then have $N\equiv N_A-N_B\pmod{2^k-1}$. So at worse, the cost for arbitrary $P$ is twice the cost for any $Q$ we see fit, plus whatever the cost of changing from $S/E\equiv x^N\pmod P$ to $A\equiv B^N\pmod Q$ is. $\endgroup$
    – fgrieu-onstrike ♦
    Jul 3, 2014 at 16:12
  • $\begingroup$ @fgrieu: you've got it mostly; however there's one point you missed. When we're switching between $GF(2^k)$ representations, we're not actually changing anything essential in the equation. Instead, a "representation" is just a way of mapping between the elements of the abstract field to bit patterns; and yes, it is fun and easy to convert the bit pattern of one representation into the exact same field element in a different representation. Also, it doesn't matter of the generator is sparse or not; as long as it is primitive, the argument works. $\endgroup$
    – poncho
    Jul 3, 2014 at 18:59
4
$\begingroup$

Don't know if this is still of interest. The fastest way I see is to precompute a basis $E_i=M^{2^i}*E$ for $i=1,...,n$ and then to solve the system of linear equations:

$$S = c_1*E_1 +...+c_n*E_n$$

The values $c_i$ give you the binary representation of $N$. The effort is $n^3$ (for the online step) and memory requirement should be roughly $n^3$ as well. The precomputation is a little bit more costly but still polynomial in $n$.

Improve this answer
$\endgroup$

Your Answer

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

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