International Association
for Cryptologic Research

In this note we discuss Reed-Solomon codes with domain of definition within the unit circle of the complex extension $\mathbb C(F)$ of a Mersenne prime field $F$. Within this unit circle the interpolants of “real”, i.e. $F$-valued, functions are again almost real, meaning that their values can be rectified to a real representation at almost no extra cost. Second, using standard techniques for the FFT of real-valued functions, encoding can be sped up significantly. Due to the particularly efficient arithmetic of Mersenne fields, we expect these “almost native” Reed-Solomon codes to perform as native ones based on prime fields with high two-adicity, but less processor-friendly arithmetic.