Finding the n-th root of unity in a finite field

Question

I'm trying to find the n-th root of unity in a finite field that is given to me. n is a power of 2. The finite field has prime order. I know that if this were just normal numbers, I could find it using $e^{(2\pi ik/n)}$. I have no idea how to translate that into finite fields.

Answer 1

In a finite field of size $q$, the multiplicative subgroup has order $q-1$ (i.e. all elements are invertible except $0$). If $n$ is relatively prime to $q-1$, then there is only one $n$-th root of unity, i.e. $1$ itself. If $n$ divides $q-1$, then there are $n$ roots of unity. In the remainder of this answer, I assume that you are in that case, i.e. $n$ divides $q-1$.

Everything I write below uses computations in the finite field (i.e. modulo $q$, if $q$ is prime).

To get an $n$-th root of unity, you generate a random non-zero $x$ in the field. Then: $$ (x^{(q-1)/n})^n = x^{q-1} = 1 $$ Therefore, $x^{(q-1)/n}$ is an $n$-th root of unity. Note that you can end up with any of the $n$ $n$-th roots of unity (including $1$ itself), each with probability $1/n$.

Now you may want to have a primitive $n$-th root of unity, i.e. one value $g$ such that all $n$-th roots of unity can be obtained with values $g^j$ for integers $j$ ranging from $0$ to $n-1$. If $g$ is an $n$-th root of unity, then it is primitive if and only if $g^j \neq 1$ for any $j > 0$ that divides $n$, except $n$ itself. In your case this is easy: since $n$ is a power of $2$, any $j$ that divides $n$ is also a power of $2$. In practice, this yields the following:

• Get a random $x \neq 0$ in your finite field.
• Compute $g = x^{(q-1)/n}$.
• If $g^{n/2} \neq 1$, then $g$ is a primitive $n$-th root of unity. Otherwise, start again with another random $x$.

This will succeed with probability $1/2$ at each iteration, so you'll get your primitive root rather quickly. Also, you don't need a strongly secure randomness generator here (unless the choice of the primitive root is to be part of some secret).

Take care that there are several primitive $n$-th roots of unity; in your case, there are precisely $n/2$ of them. None of them is more primitive than the others; thus, there is no notion of "the primitive root". You find a primitive root.