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.