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

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.

• But you are working in the multiplicative group, which has not prime order. See also this answer – Ruggero Oct 31 '18 at 16:01
• @Ruggero: actually, there do exist finite fields with prime-sized multiplicative groups; for example, $GF(2^{127})$. – poncho Oct 31 '18 at 16:32
• @Ruggero The group I'm working with is certainly prime order. – picotard Oct 31 '18 at 16:35
• 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$ – poncho Oct 31 '18 at 18:29
• @poncho Ops. I confess my mind is often limited to prime fields. – Ruggero Nov 5 '18 at 9:57

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.

• No, this is valid for all finite fields. Note that a 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. – Thomas Pornin Nov 1 '18 at 0:03