Contest problems with connections to deeper mathematics

This question is with regard to Elkies' answer to the above post.

What is the complexity of computing the Moore matrix modulo some integer? Vandermonde determinant can be computed in $O(n\log{n})$? Can it be reduced from $O(n^{3})$ and is it the same as $O(n\log{n})$ for Moore (if so is there a reference)?