I need to evaluate a polynomial of degree n at the n cube roots of unity. Simple evaluation would take $O(n^2)$ time. I know that polynomial evaluation can be done in $O(n\log n)$ time using FFT.
But the problem that I am facing is this. FFT only works when $n$ is a power of 2. If I extend my polynomial by appending zeroes at the end, that would not solve my problem because then I would be evaluating my polynomial at cube roots of $m$ (where $m$ is a power of $2$ greater than $n$) which I don't want.
Any ideas on this?