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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Umm, $\mathbb{Z}/p$ is not algebraically closed ... $\endgroup$– David Roberts ♦Commented Dec 5, 2012 at 23:31
-
$\begingroup$ 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? $\endgroup$– David Roberts ♦Commented Dec 5, 2012 at 23:32
-
$\begingroup$ 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. $\endgroup$– codegeek234Commented Dec 5, 2012 at 23:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
6$\begingroup$ 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 $\endgroup$ Commented Dec 6, 2012 at 1:26
-
$\begingroup$ @Felipe. Should I have kept my mouth shut? $\endgroup$– ACLCommented Dec 7, 2012 at 22:42