0
$\begingroup$

Why $x^4+x^3+x^2+x+1$ has root order 1 or 5 in $GF(2)$?

For example: $P(x)=x^4+x^3+x^2+x+1$ is irreducible over $GF(2)$. Note, that $(x^5-1)=(x-1)(x^4+x^3+x^2+x+1)$. Those, any root of $P(x)=0$ has order 5 or 1.

Why?

  • 0
    If $x^4+x^3+x^2+x+1=0$, then $x^5-1=0$ or $x^5=1$. So the least $n$ with $x^n=1$ is a factor of $5$, and thus either $n=1$ or $n=5$.2012-04-06

1 Answers 1

1

Here the order of a root $\alpha$ clearly means the order of $\alpha$ in multiplicative group $GF(2)[\alpha]^*$. IOW, the order of $\alpha$ is the smallest positive integer $m$ such that $\alpha^m=1$. So let us assume that $P(\alpha)=0$, where $\alpha$ belongs to some extension field $GF(q)$, $q$ a power of two.

The factorization that you gave $ x^5-1=(x-1)P(x) $ shows that $ \alpha^5-1=(\alpha-1)P(\alpha)=(\alpha-1)\cdot0=0. $ Therefore $\alpha^5=1$. From the basic theory of cyclic groups we know that the order of $\alpha$ must then be a factor of five, i.e. either five or one. The latter possibility is easy to exclude. If $\alpha$ were of order one, then $1=\alpha^1=\alpha$. But $P(1)=5=1\neq0$, so $1$ is not a zero of $P(x)$.

  • 0
    @Sergey, sorry about missing that last question. It is possible, but computationally somewhat taxing. For example, if you know that $P(x)$ is irreducible, then the order will be a factor of $2^{\deg P(x)}-1$, but will not be a factor of any smaller number of the form $2^k-1$. That still leaves you many cases, but does cut down the work. If $P(x)$ is not irreducible, then the question becomes a bit ill-defined in the sense that the answer typically depends on the choice of the root $\alpha$. We should then really replace $P(x)$ with the minimal polynomial of $\alpha$.2012-04-11