Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 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
up vote 2 down vote accepted

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.

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

Your Answer


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.