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? 



Primitive $k$th root of unity in a finite field $\mathbb{F}_p$
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.


