## Primitive $k$th root of unity in a finite field $\mathbb{F}_p$

I am given a prime $p$ and another number $k$ ($k$ is likely a power of $2$). I want an efficient algorithm to find the $k$th root of unity in the field $\mathbb{F}_p$. Can someone tell me how to do this?

-
 Umm, $\mathbb{Z}/p$ is not algebraically closed ... – David Roberts Dec 5 at 23:31 And when you say "the" $k^{th}$ root of unity, you know there are $k$ of them, and they are not all equal in status? – David Roberts Dec 5 at 23:32 Clarification: sorry my notation isn't perfect. I meant the finite field F_p i.e., a set of integers between {0, 1, ... p-1} where p is a prime. Basically, I am doing FFT over a finite field with k elements. Doing so requires me to first find a primitive kth root of unity in F_p, right? so, my question is how do I do it. Most descriptions of FFT assume that the primitive root is known. – codegeek234 Dec 5 at 23:40

Presumably, you are assuming that $k$ divides $p-1$, so that there is effectively a primitive $k$th root of unity in ${\bf F}_p$, even $\phi(k)$ of them ($\phi$ is Euler's totient function). The simplest method I know to get your hand on one is as follows.

A. Factor $k=\ell_1^{n_1}\dots \ell_r^{n_r}$ as a product of distinct prime numbers with exponents.

B. For every $i=1,\dots,r$, do the following: Take a random element $x$ in ${\bf F}_p$ and compute $x^{(p-1)/\ell_i}$ in $F_p$, until the result is different from $1$. Then set $a_i=x^{(p-1)/\ell_i^{n_i}}$.

C. Set $a=a_1 a_2\cdots a_r$. This is a primitive $k$th root of unity in ${\bf F}_p$.

In practice, $k$ should be a power of $2$, $k=2^n$, so that $r=1$ and you only have to repeat step B once.

-
This is the wrong website for these kind of questions. Try math.stackexchange.com. Meanwhile, here is a 256-bit prime p with p-1 divisible by 2^32. 115792089237316195423570985008687907853269984665640564039457584008797892902913 – Felipe Voloch Dec 6 at 1:26
@Felipe. Should I have kept my mouth shut? – ACL Dec 7 at 22:42