Let $P\in\mathbb{F}_p[T]$ (not supposed irreducible). All roots $\xi$ of $P$ have a certain order $k$ such that $\xi^k=1$.
Question: is it possible to know the order of the roots of the given polynomial $P$, or at least a upper bound of the order?
It is clear that if $k$ is an order of (a root of) $P$ then by the description of factors of cycltomic polynomials $\Phi_k$ then
$$ \text{ord}_k(p)\leq \deg(P) $$
where $\text{ord}_k(p)$ is the order of $p$ in $(\mathbb{Z}/k\mathbb{Z})^*$ and that basically
$$ \log_p(k)\leq \text{ord}_k(p) $$
because for $a$ to be the order of $p$ we must have $p^a\geq k$.
So we have
$$ \log_p(k)\leq\deg(P) $$
and hence
$$ k\leq p^{\deg(P)} $$
This is a very big upper bound and for algorithms I would like to have a smaller bound or better a list of possible orders.
Thanks for your help!
Best Answer
Let $d = \deg P$. The list of possible orders is simply the list of divisors of $p^d-1$.
Proof that every such order appears: Let $n$ divide $p^d-1$. Let $\alpha$ be an element of $\mathbb F_{p^d}$ of order $n$, which exists since the multiplicative group of $\mathbb F_{p^d}$ is cyclic. Then $\alpha$ generates a subfield $\mathbb F_{p^e} \subseteq \mathbb F_{p^d}$ for some divisor $e$ of $d$. The minimal polynomial of $\alpha$ has degree $e$, so the $d/e$th power of it does the trick.
Proof that these are the only such orders that appear. Let $P$ be such a polynomial, and let $e$ be the least natural number such that $k$ divides $p^e-1$. Then every element of $\overline{\mathbb F_p}$ of order $k$ lies in $\mathbb F_{p^e}$, and none of them lie in any smaller finite field, so they all have minimal polynomials of degree $e$. Since $P$ has roots only these elements, $P$ is a product of these minimal polynomials, so $\deg P$ is a multiple of $e$. Thus $p^{ d}-1$ is a multiple of $p^e-1$ and hence is a multiple of $k$.
So your upper bound is sharp, but despite this, there is a list of size $p^{ o(d)}$ (by bounds for the divisor function).