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.

  • 1
    $\begingroup$ But you are working in the multiplicative group, which has not prime order. See also this answer $\endgroup$
    – Ruggero
    Commented Oct 31, 2018 at 16:01
  • 2
    $\begingroup$ @Ruggero: actually, there do exist finite fields with prime-sized multiplicative groups; for example, $GF(2^{127})$. $\endgroup$
    – poncho
    Commented Oct 31, 2018 at 16:32
  • $\begingroup$ @Ruggero The group I'm working with is certainly prime order. $\endgroup$
    – fraiser
    Commented Oct 31, 2018 at 16:35
  • $\begingroup$ If the multiplicative group you're working in has prime order and n is a power of 2, then the answer is easy; either you're working in $GF(3)$ (and so the answer is 1 and 2), or you're working in a larger group, in which case the only n-th root of 1 is 1, that is $x^n = 1$ only if $x=1$ $\endgroup$
    – poncho
    Commented Oct 31, 2018 at 18:29
  • $\begingroup$ @poncho Ops. I confess my mind is often limited to prime fields. $\endgroup$
    – Ruggero
    Commented Nov 5, 2018 at 9:57

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

  • $\begingroup$ Note that any finite field has order $q = p^f$ for a prime $p$ and an integer $f$. When $q$ is not prime (i.e. $f > 1$), the finite field of cardinal $q$ is not the ring of integers modulo $q$. I am talking about the field, not the ring. $\endgroup$ Commented Nov 1, 2018 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.