# Fastest Way to Find order of element in Finite Fields?

Two questions:

I use Miller-Rabin to find a prime, p, close to an arbitrary input number (this is very fast). Then I use Floyd's cycle finding algorithm to find the order of a randomly chosen element in F_p.

If p is large, this takes a long time.

I am not interested in using particular p such that 2 is always a primitive root. I am interested in the fastest way to find the order of an element. Is there any better methods than Floyd's (or Brent's)?

Second question: Given that x^n - 1 = 0 (mod p) for x being an nth root of unity, is there any use in using some of the various polynomial root finding algorithms to solve that equation for either x given n, or for n given x?

Feel free to refer to Wikipedia/Google but some expert guidance will surely cut down my search time and short-cut me past the wrong directions.

-
Can you factor $p-1$ and $n$? – Hurkyl Dec 12 '12 at 13:37
@Hurkyl Yes. This should not be a problem. I guess that the order of any element must be a multiple of one of the divisors of p-1...is this your idea? And then how to proceed ? Try out all the possible orders for an element? Please explain more. – Cris Stringfellow Dec 12 '12 at 13:40

The easiest way to find the order of an element is to test $\alpha^n = 1$ for $n \mid p-1$.

If that's not fast enough, I'm sure there are tricks you can play by testing the $n$'s in a clever order, or using Chinese Remainder Theorem tricks to work on each prime factor of $p-1$ individually.

For finding an $n$-th root of unity with $n \mid p-1$, the simplest algorithm is probably to simply choose $\alpha$ randomly and compute $x = \alpha^{(p-1) / n}$, which is guaranteed to be an $n$-th root.

If you need a primitive $n$-th root, then you check the order of $x$ (but you only have to check divisors of $n$. Again, there are probably tricks you can do if that turns out not fast enough.

-
Great.Thanks. This works. – Cris Stringfellow Dec 12 '12 at 13:53
Please correct me if I'm wrong, but it seems we can compute and check the order of an arbitrary element very quickly (simply by knowing dividers of p-1 and n). What if our field is actually direct product of F_p and F_q, with p and q unknown. Can we not then compute the order of an arbitrary element in this field, and hence factor n=pq? What prevents this from happening? – Cris Stringfellow Dec 12 '12 at 14:01
$\mathbb{F}_p \times \mathbb{F}_q$ isn't a field. But the algorithm I described works for invertible elements of $\mathbb{Z} / N$ too if you use $\varphi(N)$ instead of $p-1$ -- but to find $\varphi(N)$, you have to already know the factorization of $N$. – Hurkyl Dec 12 '12 at 14:06
Yep. I worked that out myself as I was asking a question. So I just posted another questions asking what is the best way to find such orders without knowing the order of FpxFq. – Cris Stringfellow Dec 12 '12 at 14:18