Find a collection of values of polynomial

Given a polynomial $$f(x)\in \mathbb C[x]$$ where $$\deg f(x)=n-1.$$ Assume that we need to find a collection of values of this polynomial corresponding to the following set of $$x$$-values: $$\{ e^{ik} \}$$ where $$k= 0, …, n-1,$$ and $$i$$ denotes the imaginary unit.

There is an algorithm that can solve this problem for any collection of $$x$$-values using FFT in $$O(n\log^2(n)).$$ On the other hand, if all $$x$$-values are $$n$$ - roots of unity, then FFT can solve the problem in $$O(n\log n).$$

Question: Is it possible to solve the above problem in $$O(n\log n)$$ as well?

Hint: Use the equation $$e^{ikl}=e^{i\frac{k^2}{2}}e^{-i\frac{(k-l)^2}{2}}e^{i\frac{l^2}{2}}$$ and properties of Toeplitz matrices.