How do I find the order of an element if I am given the minimal polynomial of the element?

Question

For example, let's say I am given an element $α$ in a field of characteristic $2$. Further, I am given the minimal polynomial of α with respect to $GF(2)$. Let's say that minimal polynomial is $f(x) = x^9 + x + 1$. How would I then deduce the order of $α$?

This is for a coding theory assignment, but I cannot deduce from the literature how to go in this direction. Most things I have read seem to indicate how to find a minimal polynomial, but don't seem to take that any further.

Answer 1

You have $\alpha^9 = \alpha + 1$. Squaring, you get $(\alpha^9)^2 = (\alpha+1)^2 = \alpha^2+1$, and squaring again twice yields $(\alpha^9)^8 = \alpha^8+1$. Multiplying by $\alpha$, you get $\alpha^{8 \cdot 9+1} = \alpha^9 + \alpha = 1$, hence the order of alpha divides $8 \cdot 9 + 1 = 73$, which is prime.

EDIT: I just thought of a way to expand on this. Since $[\mathbb{F}_2(\alpha):\mathbb{F}_2] = 9$, we have $\mathbb{F}_2(\alpha) \cong \mathbb{F}_{2^9}$ meaning that the order of $\alpha$ divides $|(\mathbb{F}_{2^9})^\times| = 511 = 7 \cdot 73$ by Lagrange's theorem. If the order were $7$, then we would have $\alpha^7-1=0$ and thus $X^7-1$ would divide the minimal polynomial of $\alpha$, which is clearly not the case. Thus, the only possibilities are $73$ and $511$, and since we saw that $\alpha^{73}=1$, we get the answer.

It would be interesting to know if we can get this result without the computation from the beginning though.

Answer 2

As a minor variation on hrt's answer:

We know that $\alpha^9 = \alpha + 1$. Since $(a+b)^{2^m} = a^{2^m} + b^{2^m}$ in a field of characteristic $2$, we have that \begin{align} (\alpha^9)^8 &= (\alpha + 1)^8\\ &= \alpha^8 + 1\\ &\Downarrow\\ \alpha^{72} &= \alpha^8+1\\ &\Downarrow\\ \alpha^{73} & = \alpha^9+\alpha\\ &= 1. \end{align} Thus, $\mathsf{ord}(\alpha)$ is $73$ or a factor thereof, and since $73$ is a prime and $\alpha \neq 1$, it must be that $\mathsf{ord}(\alpha)=73$.

The answer is not so easy to get at in general: this particular case leads to a simple calculation. Try finding the order of the roots of $x^4+x^3+1 \in \mathbb F_2[x]$ using the above "trick" to see what I mean.The period of a polynomial $f(x) \in \mathbb F[x]$ is defined to be the smallest integer $n$ such that $f(x)$ is a divisor of $x^n-1$, and if $f(x)$ is an irreducible polynomial of degree $m$, then $n$ is a divisor of $|\mathbb F|^m-1$.