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