1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Umm, $\mathbb{Z}/p$ is not algebraically closed ... $\endgroup$
    – David Roberts
    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
    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$ Dec 5, 2012 at 23:40

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
2
  • 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$ Dec 6, 2012 at 1:26
  • $\begingroup$ @Felipe. Should I have kept my mouth shut? $\endgroup$
    – ACL
    Dec 7, 2012 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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