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?
On
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.
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$.