3
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thomas Pornin Nov 1 '18 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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