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
    It may mean order as an element of the multiplicative group of an appropriate extension field.2012-04-06
  • 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
    $GF(16)$ is the smallest extension field $GF(q)$ of $GF(2)$ with the property that $5\mid(q-1)$. It follows relatively easily that $P(x)$ has four distint zeros in the field $GF(16)$.2012-04-06
  • 1
    And the presence of $GF(2)$ in the question is a red herring. The conclusion (that the order of a root is either $1$ or $5$) is true in whatever ring $x$ can be evaluated to to make $P(x)=0$.2012-04-06
  • 0
    @Lubin, you are, of course, correct. The question is more meaningful in a finite field though. Mostly because in a finite field **all** non-zero elements have a finite order. With the present polynomial it doesn't matter, because $P(x)$ is the fifth cyclotomic polynomial.2012-04-06
  • 0
    @JyrkiLahtonen, thank You for answer! But I have one more. Is it possible to determine the root order of any polynomial?2012-04-07
  • 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