# Determine every degree 4 primitive polynomial in $GF(2)[x]$

Determine, showing all reasoning, every degree 4 primitive polynomial in $GF(2)[x]$.

I think $x^4+x+1$ might be one but I do not know how to show it, could anyone explain?

Also after this, how would I know that I have found every one?

To show that $f = x^{4} + x + 1$ is primitive, first of all check it is irreducible. (You may skip this, see below.)

You will want to show that

1. it has no roots in $GF(2)$ (so it has no factor of degree $1$ in $GF(2)[x]$), and then
2. you will have to check that it has no irreducible factor of degree $2$ - this will be easy, as there are not many such polynomials.

Then check it is primitive, by computing the multiplicative period of $x$ modulo $f$. This second check will also prove independently that $f$ is irreducible, if you know the argument.

There is another primitive polynomial, which is $x^{4}(f(x^{-1}))$.

To see that there no others, you may check that the multiplicative group of $GF(2^{4})$, which is cyclic of order $2^{4} - 1 = 15$, has exactly $\phi(15) = 2 \cdot 4 = 8$ generators. Hence they are all covered by the two polynomials.

• Could you possibly show me an example of this step: 'Then check it is primitive, by computing the multiplicative period of $x$ modulo $f$'. I don't quite understand it. Feb 17, 2017 at 17:09
• Your multiplicative group is of order $15$, and cyclic. If something is not of order $15$, it’s of order three or five (or it’s trivial). Just check that $x^3\not\equiv1\pmod{x^4+x+1}$ and $x^5\not\equiv1\pmod{x^4+x+1}$, Feb 17, 2017 at 17:32
• @Lubin How come we have to show it for $x^3$? Is this not trivial since $x^3$ is a smaller degree than $x^4+x+1$ Feb 17, 2017 at 21:58
• @Andreas Caranti when you say there are 8 generators are these, $\{1,0,x,x^2,x^3,x^4,x^4+x^3+1,x^4+x+1\}$? Feb 17, 2017 at 22:11
• The checking that $x$ is not of order three is indeed trivial. But it needs to be done, even if by pure thought. Feb 17, 2017 at 23:09

The product of every monic irreducible polynomial over $\mathbb{F}_2$ with degree $1,2$ or $4$ is given by $x^{2^4}-x$ and the product of every monic irreducible polynomial with degree $1,2$ is given by $x^{2^2}-x$. It follows that the product of every monic irreducible polynomial over $\mathbb{F}_2$ with degree four is given by: $$\frac{x^{16}-x}{x^4-x} = \left(1+x+x^2+x^3+x^4\right) \left(1-x+x^3-x^4+x^5-x^7+x^8\right)$$ and the only monic irreducible polynomials with degree $4$ are $$1+x+x^2+x^3+x^4,\quad 1+x^3+x^4,\quad 1+x+x^4.$$