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

  • $\begingroup$ 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. $\endgroup$ – Felipe Voloch Feb 13 '13 at 17:05
  • 1
    $\begingroup$ 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) :-) $\endgroup$ – 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$.

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

| cite | improve this answer | |
  • $\begingroup$ 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$? $\endgroup$ – QQQ Feb 13 '13 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.