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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ We have a lot of related material. I haven't checked the sources, but here are links to some on-line stuff. $\endgroup$– Jyrki LahtonenFeb 17, 2017 at 18:48
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
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
- it has no roots in $GF(2)$ (so it has no factor of degree $1$ in $GF(2)[x]$), and then
- 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.
answered Feb 17, 2017 at 14:44
-
1$\begingroup$ 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. $\endgroup$– harry55Feb 17, 2017 at 17:09
-
2$\begingroup$ 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}$, $\endgroup$– LubinFeb 17, 2017 at 17:32
-
$\begingroup$ @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$ $\endgroup$– harry55Feb 17, 2017 at 21:58
-
$\begingroup$ @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\}$? $\endgroup$– harry55Feb 17, 2017 at 22:11
-
2$\begingroup$ The checking that $x$ is not of order three is indeed trivial. But it needs to be done, even if by pure thought. $\endgroup$– LubinFeb 17, 2017 at 23:09
$\begingroup$
$\endgroup$
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.$$
answered Feb 17, 2017 at 16:09