  This paper presents a new construction of Maximum-Distance Separable (MDS)
Reed-Solomon erasure codes based on Fermat Number Transform (FNT). Thanks to
FNT, these codes support practical coding and decoding algorithms with
complexity O(n log n), where n is the number of symbols of a codeword. An
open-source implementation shows that the encoding speed can reach 150Mbps for
codes of length up to several 10,000s of symbols. These codes can be used as
the basic component of the Information Dispersal Algorithm (IDA) system used in
a several P2P systems.
