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

Question

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)$.