# Order of an element in a finite field

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).

• If the field has $q$ elements and you can factor $q-1$, then computing $\alpha^d$ for all divisors $d$ of $q-1$ is fast and will give the order. Factoring, unfortunately, can be hard. – Felipe Voloch Feb 13 '13 at 17:05
• If you read the introduction to that paper, they talk about Adleman and DeMarrais's subexponential algorithm for discrete logs in finite fields. The paper itself just describes a probabilistic polynomial time reduction. I don't think anyone knows how to do discrete logs for finite fields in polynomial time (in $\log q$, of course) :-) – Abhinav Kumar Feb 13 '13 at 19:01

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$.
• I agree, that works if we are given the prime power factorization of $p^n-1$. But is it always easy to find prime factors for numbers of the form $p^n-1$? – QQQ Feb 13 '13 at 17:15