  In this paper, we present a new basis of polynomial over finite fields of
characteristic two and then apply it to the encoding/decoding of Reed-Solomon
erasure codes. The proposed polynomial basis allows that $h$-point polynomial
evaluation can be computed in $O(h\log_2(h))$ finite field operations with
small leading constant. As compared with the canonical polynomial basis, the
proposed basis improves the arithmetic complexity of addition, multiplication,
and the determination of polynomial degree from $O(h\log_2(h)\log_2\log_2(h))$
to $O(h\log_2(h))$. Based on this basis, we then develop the encoding and
erasure decoding algorithms for the $(n=2^r,k)$ Reed-Solomon codes. Thanks to
the efficiency of transform based on the polynomial basis, the encoding can be
completed in $O(n\log_2(k))$ finite field operations, and the erasure decoding
in $O(n\log_2(n))$ finite field operations. To the best of our knowledge, this
is the first approach supporting Reed-Solomon erasure codes over
characteristic-2 finite fields while achieving a complexity of $O(n\log_2(n))$,
in both additive and multiplicative complexities. As the complexity leading
factor is small, the algorithms are advantageous in practical applications.
