# Chossing a prime for fft of size $2^n$

I have a $p$ degree polynomial where $p$ is prime, I want to find the value of this polynomial at all points from $1$ to $p-1$,to make the fft on this polynomial easier I padded it with zeroes up to length to the next power of $2$ greater than p(note that here $p$ and $n$ are both large, the padded length is $2^{20}$ here $p-1$ is a multiple of power of $2$), now I should find the value of this polynomial from $0$ to $2^{20}-1$ but since $2^{20}$ has no primitive root, I cannot do fft on this size. So my question is how do I proceed. I tried finding primitive root of $2^{20}$ modulo some prime $p_2$ of the form $k\cdot 2^{20} +1$, but doing so, the $n$ powers of that primitive root${}^k$ did not give me all values from $0$ to $n-1$. How should I deal with this problem? Although my approach might be wrong new methods are welcome, the original goal is to find value of the polynomial at all points from $0$ to $p-1$ in time $O(n\log n)$.

• What is $n$ here? The first mention of it is that it is large – Hagen von Eitzen Jul 11 '16 at 4:41
• n here is the padded length of 2^20 – user346777 Jul 11 '16 at 4:42
• Ah, so with $n\approx 2p$ we have $n=O(p)$ and so your really original goal is $O(p\log p)$, I presume – Hagen von Eitzen Jul 11 '16 at 4:43
• yes that is my primary goal! – user346777 Jul 11 '16 at 4:44
• That's an ambitious goal. Merely writing out $p$ values in the range $0,\ldots,p-1$ takes $O(p\log p)$ time. – Hagen von Eitzen Jul 11 '16 at 4:47