Primitive $k$th root of unity in a finite field $\mathbb{F}_p$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T04:14:13Z http://mathoverflow.net/feeds/question/115560 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115560/primitive-kth-root-of-unity-in-a-finite-field-mathbbf-p Primitive $k$th root of unity in a finite field $\mathbb{F}_p$ codegeek234 2012-12-05T23:28:31Z 2012-12-07T17:59:21Z <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? </p> http://mathoverflow.net/questions/115560/primitive-kth-root-of-unity-in-a-finite-field-mathbbf-p/115561#115561 Answer by ACL for Primitive $k$th root of unity in a finite field $\mathbb{F}_p$ ACL 2012-12-05T23:52:48Z 2012-12-05T23:52:48Z <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.</p> <p>A. Factor $k=\ell_1^{n_1}\dots \ell_r^{n_r}$ as a product of distinct prime numbers with exponents. </p> <p>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}}$.</p> <p>C. Set $a=a_1 a_2\cdots a_r$. This is a primitive $k$th root of unity in ${\bf F}_p$.</p> <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.</p>