Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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
add comment

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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