What is the most efficient algorithm to evaluate a polynomial of n degree at K points? A brute force approach would be to evaluate each point for each of the terms of a polynomial, which will be $O(Kn^2)$.
If we use logarithmic exponentiation to find each $x^i$ then it becomes $O(Kn \log n).$
As Phicar suggested, Horner's method is another order improvement; doing this in  $O(Kn)$.
But I believe it is possible to do it in $O(K \log^2(n))$, which I don't understand yet.
I will tell you where I came across this. https://fredrikj.net/blog/2012/03/factorials-mod-n-and-wilsons-theorem/ . On the 4th paragraph it says "FFT-based
polynomial multiplication and balanced subproduct trees".
Here also  on 4th paragraph, it says "This algorithm of substituting many points into one polynomial is described in the book "Prime numbers" by C. Pomerance and R. Crandall".
 A: Here’s a book that describes how to do it:  http://www.cecm.sfu.ca/CAG/theses/justine.pdf
Here’s a brief summary. Using FFT, you can  $n \log n$ quickly multiply polynomials of size $n$.
You can also use FFT to divide polynomials by first inverting then and then multiplying. Intuitively, if you have a Taylor series $1+a_1 x+a_2 x^2…$, then you can invert it to get another Taylor series  where the coefficients can be quickly calculated using Newton Inversion. Calculating the first $n$ coefficients of this series takes $n \log n$ time using FFT in that algorithm.
Combining polynomial inversion with multiplication lets you in a certain sense divide polynomials quickly. Doing it rigorously let’s you compute $f(x) \mod g(x)$ quickly.
Evaluating a polynomial $f(x)$ at $a$ is equivalent to $f(x) \mod x-a$.   Just like taking something mod 6 and then mod 2 gives the same final answer, you can take $f(x) \mod g(x)h(x)$ and then take it mod each polynomial to get the same answer. This is useful since each secondary quotient deals with smaller polynomials, so the entire calculation ends up  being quicker.
Consider a big binary tree of height $\log n$ whose leaves are the $K$ linear polynomials $x-a_i$. Let each node be the product of the polynomials of it’s two children, so that the top level node is $(x-a_1)(x-a_2)…(x-a_K)$. This is known as a sumproduct tree.
By moving up the tree from leaves to nodes and multiplying, you can quickly calculate the polynomial at each node. By taking your function $f$ and taking the remainder after dividing by each node’s polynomial and moving down from each node to its children, you can calculate the remainder at each leaf node and so get the desired evaluations.
At the $j$th layer (ignoring the root for now), there are $2^j$ multiplications/divisions between polynomials of length $K/2^j$ each of which takes  $ K/2^j \log (K/2^j)$, so this takes $\sum_j 2^j K/2^j \log(K/2^j) \leq \sum_j K\log(K)= K (\log(K))^2$ time.
The root requires a polynomial quotient between a polynomial of length $N$ and $K$. This takes the maximum of $N \log K$ and $K \log N$. If $K>N$ then the rest of the calculation dominates. If $N<K$, it takes $N\log K$. Combining gives an overall complexity of at most $N \log K + K (\log(K))^2$
