How do we find polynomial order?

Question

I read Polynomial order defination, but i am still confuse how do we find polynomial order if we have a polynomial. What does Polynomial order represent?

How do we find polynomial order if we have polynomial forexample $x^{5}+x^{2}+1$, currently it has order 31 but i don't know how?

Answer 1

You want the minimum $n$ such that

$$\frac{x^n+1}{x^5+x^2+1}$$

In $\mathbb{F}_2$.

Doing the division without knowing the $n$ (only trying to get residue zero), you have that the polinomial $x^n+1$ will let you the quotient

$$x^{n-5}+x^{n-8}+ x^{n-10}+x^{n-11}+x^{n-14}+x^{n-15}+x^{n-16}+x^{n-17}+x^{n-18}+x^{n-22}+x^{n-23}+x^{n-25}+x^{n-26}+x^{n-27}+x^{n-29}+x^{n-31}$$

Because:

\begin{align*} x^n & +x^{n-3} & +x^{n-5}\\ & +x^{n-3}&& +x^{n-6}&+x^{n-8}\\ && x^{n-5}&&+x^{n-8}&+x^{n-10}\\ &&&&... \end{align*}

(Is a very large division)

So you only want the minimal $n$ for which this division has residue zero, so you just only need to do $n-31=0$, and you will get exactly $n=31$ and the polynomial that is the quotient of the equation will be:

$$1+x^2+x^4+x^5+x^6+x^8+x^9+x^{13}+x^{14}+x^{15}+x^{16}+x^{17}+x^{20}+x^{21}+x^{23}+x^{26}$$

If you consider any $n>31$, the minimal is this one. If you consider any $n<31$, the division won't have sense since you need to get that $n-31>0$.

Answer 2

Let's write $F$ for the field of two elements, and $f(x)$ for $x^5+x^2+1$. You have to show $f$ is irreducible over $F$. Having done that, it follows that $K=F[x]/\langle\,f\,\rangle$ is a field of degree 5 as an extension of $F$. It follows that $K$ has $2^5=32$ elements. So there are 31 nonzero elements. The nonzero elements of any field form a group, so in this case it's a group of order 31. Now 31 is a prime, so every element of this group has order 31 (except, of course, the multiplicative identity, which has order 1).