Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Say you have a characteristic polynomial of an LFSR:

$$f(X) = X^4 + X^3 + 1$$

How can I use this function f to get the output of the LFSR, given some initial state?

Obviously I can create the LFSR diagram based on the function, since this function describes where the "taps" are (see .e.g the Wikipedia article http://en.wikipedia.org/wiki/LFSR):

|----+--------+
|    |        |
+-->[0][1][1][0]-->

Then calculate it iteratively like this: 0, 1, 1, 0, 0, ... (here the initial state is as in the diagram, 0,1,1,0).

I know you can also get this output from the equation:

$$s_j \equiv c_1s_{j-1} + c_2s_{j-2} + \dots + c_2s_{j-2} \pmod 2$$

Which gives the same result as calculating it from the diagram "by hand".

However my question is how to get this from the characteristic polynomial. Also what purpose does the characteristic polynomial have, beyond describe the taps in this way? If you give f some arbitrary argument, what are you really doing? What is the argument X?

I have a feeling this should be covered pretty well in some readily accessible online guide or tutorial that I cannot find, however I have read several such texts and searched through several more, and this is still not clear to me.

share|improve this question
    
One of the purposes of the characteristic polynomial is to prove that the LFSR generates a sequence of maximal length if and only it (the characteristic polynomial) is primitive. I talk a bit about it here. –  fkraiem Mar 26 at 3:24

1 Answer 1

up vote 4 down vote accepted

The variable of a polynomial is traditionally noted $x$, not $X$; and, when dealing with LFSRs, the polynomial is seldom considered a function. Thus I'll rewrite the polynomial as $P(x)=x^4+x^3+1$, a polynomial of degree $n=4$.

This is a polynomial with coefficients in the field $\operatorname{GF}(2)$, also noted $\mathbb Z_2$ or $(\{0,1\},+,\cdot)$ [note: in $\operatorname{GF}(2)$, $1+1=0$, and $-$ is the same as $+$]. The polynomial's coefficients are all either $0$ or $1$, and not shown: a term $x^j$ is present when its coefficient is $1$, and absent when its coefficient is $0$. When performing polynomial arithmetic, we are manipulating polynomials irrespective of the value and domain of their variable and result, unless otherwise stated.


The state of the LFSR is a polynomial $S(x)$ with coefficients in $\operatorname{GF}(2)$ of degree at most $n-1$, but can also be thought as:

  • A vector of $n$ bits $(s_0,s_1,\dots,s_{n-1})$ that are the coefficients of $S$ starting from the constant term going up to higher order terms, that is with $S(x)=\sum_{j=0}^{n-1}s_j\cdot x^j$ with the convention that $x^0=1$;
  • The integer $\hat S=\sum_{j=0}^{n-1}s_j\cdot 2^j$; addition of polynomials becomes bitwise eXclusive-OR, and multiplication of polynomials becomes carry-less multiplication [performed as binary multiplication, but replacing additions with bitwise eXclusive-OR]; the same integer can be defined as $\hat S=S(2)$ [note: here we are considering $S$ as a polynomial function over $\mathbb Z$].

The next state of the LFSR is, by definition, the remainder of the polynomial division of the polynomial $x\cdot S(x)$ by the polynomial $P(x)$, noted $\big(x\cdot S(x)\big)\bmod P(x)$.
By definition of polynomial division, the remainder of the division of polynomial $T(x)$ by non-zero polynomial $P(x)$ is the polynomial $R(x)$ of degree less than $P(x)$ such that there exists a polynomial $Q(x)$ with $T(x)=P(x)\cdot Q(x)+R(x)$.
In the context of moving to the next step of a LFSR, $Q(x)$ is either $Q(x)=1$ [when $S$ is of degree $n-1$] or $Q(x)=0$ [otherwise]; thus the next state $\big(x\cdot S(x)\big)\bmod P(x)$ is either $x\cdot S(x)+P(x)$ [when $S$ is of degree $n-1$] or $x\cdot S(x)$ [otherwise].

For example, if the initial state of the LFSR is $S_0(x)=x^2$,

  • the first non-initial state is $S_1(x)=\big(x\cdot S_0(x)\big)\bmod P(x)=\big(x\cdot x^2\big)\bmod P(x)=x^3\bmod P(x)=x^3$.
  • the second non-initial state is $S_2(x)=\big(x\cdot S_1(x)\big)\bmod P(x)$ that is $\big(x\cdot x^3\big)\bmod P(x)=x^4\bmod P(x)=x^3+1$, with the last step because $x^4=P(x)\cdot Q(x)+x^3+1$ with $Q(x)=1$, and we can obtain $x^3+1$ as $x^4+P(x)=x^4+x^4+x^3+1=x^3+1$.
  • $S_3(x)=\big(x\cdot S_2(x)\big)\bmod P(x)=\Big(x\cdot\big(x^3+1\big)\Big)\bmod P(x)$ that is $\big(x^4+x\big)\bmod P(x)=x^4+x+P(x)=x^3+x+1$.
  • $S_4(x)=\big(x\cdot S_3(x)\big)\bmod P(x)=\Big(x\cdot\big(x^3+x+1\big)\Big)\bmod P(x)$ that is $\big(x^4+x^2+x\big)\bmod P(x)=x^4+x^2+x+P(x)=x^3+x^2+x+1$.
  • $S_5(x)=\big(x\cdot S_4(x)\big)\bmod P(x)=\Big(x\cdot\big(x^3+x^2+x+1\big)\Big)\bmod P(x)$ that is $\big(x^4+x^3+x^2+x\big)\bmod P(x)=x^4+x^3+x^2+x+P(x)=x^2+x+1$.
  • $S_6(x)=\big(x\cdot S_5(x)\big)\bmod P(x)=\Big(x\cdot\big(x^2+x+1\big)\Big)\bmod P(x)$ that is $\big(x^3+x^2+x\big)\bmod P(x)=x^3+x^2+x$.

It is easy to perform the same calculation using either bit vectors, or integers, and that's practice in most computer programs. With integers, we define $\hat P=P(2)$ [that is $\hat P=\text{0x19}$ with our $P(x)$], and the state following $\hat S$ with $0\le \hat S<2^n$ is whichever of $(2\cdot\hat S)\oplus \hat P$ or $2\cdot\hat S$ is less [or, equivalently, less than $2^n$], where $\oplus$ is bitwise eXclusive-OR [operator ^ in C].


One common definition of the output of the LFSR is the coefficient of the term of degree $n-1$ in the states of the LFSR. The constant term is also popular when the reduction polynomial $P(x)$ has a constant term, which is the case in practice. Sometime [especially with the later convention], the initial state is not taken in consideration.

In the above example, the output of the LFSR [including the initial state $S_0(x)=x^2$] is thus
$0$, $1$, $1$, $1$, $1$, $0$, $1$...


Sometime it is used a reflected representation, where state $S(x)$ is represented by the integer $\check S=\sum_{j=0}^{n-1}s_j\cdot 2^{n-1-j}=2^{n-1}\cdot S(1/2)$ [note: here we are considering $S$ as a polynomial function over $\mathbb Q$].
This allows obtaining the output as the low-order bit of the integer representing the state [rather than its bit of rank $n-1$, which might be less easy to isolate]; and makes it possible to compute the next state without any test, using only common operators on unsigned words of size at least $n$ bits, using the C expression
S = (S>>1) ^ (P & -(S&1))
where P is $\check P=\lfloor2^{n-1}\cdot\big(P(1/2)\big)\rfloor$ [that is P of $9$ with our $P(x)$] and fits an unsigned word; >> is unsigned right shift [that's >>> in Java]; & is bitwise AND; and by definition of unary operator - over unsigned words, -U is the unsigned word such that the sum of U and -U is divisible by the smallest power of two that is not representable as an unsigned word [that's the definition of unary operator - using Two's-complement].

For example, starting from the same $S_0(x)=x^2$ and P of $9$, we have S taking the values $2$, $1$, $9$, $13$, $15$, $14$, $7$.. when applying S = (S>>1) ^ (P & -(S&1)) repeatedly, and the same output $0$, $1$, $1$, $1$, $1$, $0$, $1$.. obtained as S&1.


If we are able to do with bit vectors or integers rather than with polynomials, why are we using polynomials, even in theory?

One important reason is that $S_{i+1}=\big(x\cdot S_i(x)\big)\bmod P(x)$ gives $S_i=\big(x^i\cdot S_i(x)\big)\bmod P(x)=\Big(\big(x^i\bmod P(x)\big)\cdot S_i(x)\Big)\bmod P(x)$, and that's key to computing the $i^\text{th}$ state in time $\mathcal O(\log i)$ rather than $\mathcal O(i)$, and linking the period of the generator to properties of $P(x)$.


The schematic in the question (where the first + in reading order is a XOR gate with output on the left, and any other + is just a wire) at first does not seem to be matching what's above in this answer, which applies to the so-called Galois construction of a LFSR. That drawing uses the Fibonacci construction of a LFSR.

The two constructions give the same output, but starting from a different state. The state of a Fibonacci LFSR of degree $n$ [with polynomial $P(x)$ having a constant term] is the first $n$ bits output by the Galois LFSR with the the same polynomial [or that polynomial reflected, depending on definition of a Fibonacci LFSR].

For nice schematics of gate realizations of the two kinds of LFSR, see here.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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