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!



Order of roots for a polynomial $P\in\mathbb{F}_p[T]$
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).


