0
$\begingroup$

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.

  • 0
    @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.2012-12-12

1 Answers 1

2

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.

  • 0
    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.2012-12-12