Let $\mathbb F\_p$ be the finite field of a prime order $p$, $f(x)\in \mathbb F\_p[x]$ an irreducible polynomial, $E = \mathbb F\_p[x]/\langle f(x)\rangle$ a finite extension of $\mathbb F\_p$, $\lambda\in E$ is a zero of $f$. Is there an efficient algorithm for computing the order of $\lambda$ in $E^\ast$ or, more generally, the order of an arbitrary $\alpha\in E^\ast$?


Edit: Thanks a lot for the comments. My impression is that this problem can be computationally hard (not harder than factorization of the numbers $p^n-1$, of course).



Order of an element in a finite field
Let $n$ be the degree of $f$, so the order is a divisor of $p^n-1$. As the computation of powers in $E$ is a cheap operation, I believe the following could be suitable: If $\alpha^m=1$, then check if there is a prime divisor $r$ of $m$ with $\alpha^{m/r}=1$. If not, then $m$ is the order, and if yes, then set $m=m/r$ and repeat the process.


Start the whole thing with $m=p^n-1$.


Probably there are better ideas, but I cannot think of one. 


