# Calculate a Primitive Polynomial LFSR

I tried to search on the internet, to read my course multiple times, but the only thing I see are definitions of the primitive polynomials for an LFSR.

I have an exercise: Find the primitive polynomial of the LFSR of width 4 with longest possible period.

And I just don't know where to begin from.

By all I read, I know that it is irreducible and that the period will be $$2^4-1$$, so 15.

How do I find it?

This is a problem that is small enough that we can do it by brute force. The quartic polynomial must have $$x^4$$ and $$1$$ terms in it, and so we need to look only at $$8$$ quartics. Of these, $$x^4 + 1, x^4+x^2+1$$ can be eliminated as obvious squares, while $$x^4+x^3+x^2+1$$, $$x^4+ x^3+x+1$$, $$x^4+x^2+x+1$$ have an even number of terms in them and thus have $$1$$ as a root (i.e., are divisible by $$x+1$$). That leaves $$x^4+x+1$$, $$x^4+x^3+1$$, and $$x^4+x^3+x^2+x+1$$ as possible candidates of which we can eliminate $$x^4+x^3+x^2+x+1 = \frac{x^5-1}{x-1}$$ as having period $$5$$ and not $$15$$.
What you are obviously looking for is a primitive polynomial of degree 4 over $${\Bbb F}_2$$. There are two such polynomials, $$x^4+x+1$$ and $$x^4+x^3+1$$ (both are conjugate). There is another irreducible polynomial of degree 4 over $${\Bbb F}_2$$, $$x^4+x^3+x^2+x+1$$, but it divides $$x^5-1$$ and so is not primitive.