4
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\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
    Commented Feb 13, 2013 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
    Commented Feb 13, 2013 at 19:01
  • $\begingroup$ @FelipeVoloch a finite field element can have a prime order which is not a divisor from $q-1$. $\endgroup$
    – user2284570
    Commented Aug 18 at 23:42
  • $\begingroup$ @AbhinavKumar by to that paper. Which publication where you refering? $\endgroup$
    – user2284570
    Commented Aug 18 at 23:44

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Feb 13, 2013 at 17:15
  • $\begingroup$ @QQQ I do have examples/instance where finding factors of $p^n-1$ is indeed very hard because of large cofactors. $\endgroup$
    – user2284570
    Commented Aug 18 at 23:29
  • $\begingroup$ @QQQ in addition to this, a finite field element can have a prime order which is not a divisor from $p^n-1$ $\endgroup$
    – user2284570
    Commented Aug 18 at 23:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .