Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
Umm, $\mathbb{Z}/p$ is not algebraically closed ... –  David Roberts Dec 5 '12 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 '12 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 '12 at 23:40

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
4  
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 '12 at 1:26
    
@Felipe. Should I have kept my mouth shut? –  ACL Dec 7 '12 at 22:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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