Say we have $f(x)$, an irreducible polynomial of degree $m$ over GF(2). Let $\alpha$ be a root of $f(x)$. I want to find out the order of $\alpha$. One approach I know of is to calculate $\alpha^k$ for all $k$ that could possibly be orders (i.e. all factors of $2^m-1$). Is there another way of being able to relate the minimal polynomial to the order of the element?
Thanks.
Let $f(x)$ be an irreducible polynomial of degree $m$ over $GF(q)$, and $\alpha$ be one of its roots. I claim that: $$ \text{ord}(\alpha) = \min\{t \in \mathbb{N} \ | \ f(x) \text{ divides } (x^t-1) \text{ over } GF(q)\}. $$
Note that $f(x) | (x^{q^m-1}-1)$, so the quantity above is well-defined.
We now show that $\alpha^t = 1 \iff f(x) \text{ divides } (x^t-1).$ After this, the claim follows immediately.
$(\implies)$
Assume that $\alpha^t = 1$. Then $\alpha^t-1 = 0$. So $\alpha$ satisfies the polynomial $x^t-1$. But then $f(x) | (x^t-1)$ since $f(x)$ is the minimal polynomial of $\alpha$.
$(\impliedby)$
Assume $f(x) | (x^t-1)$. Then there is a polynomial $g(x)$ so that $$f(x)g(x) = x^t-1.$$
But then $$ 0 = f(\alpha)g(\alpha) = \alpha^t-1.$$
So $\alpha^t = 1$.