Complexity of polynomial interpolation
Fast polynomial interpolation and Fast polynomial evaluation are algorithms that seem to be discovered back in 1973. They allow to interpolate/evaluate polynomial at N arbitrary points as far as field has 2N (?) roots of unity. Both are based on Fast polynomial division. All three are $O(n\log^2 n)$ time.

Currently they are taught at university courses and I downloaded a lot of lecture notes some time ago. Unfortunately, most links are now dead. So you can download my archive from https://mega.nz/#!ugYRXIYB!T_0cKabvJpZmBNN7ym98nofPIOksqTN5XFxToSKj9Zg

Or read the only course still available at the old address:
http://people.csail.mit.edu/madhu/ST12/scribe/lect06.pdf
http://people.csail.mit.edu/madhu/ST12/scribe/lect07.pdf

Or just look for up-to-date notes among google search results of 1, 2 and 3. Or, yeah, try to understand the original paper.