Implementing Basic Arithmetic in $\mathbb{F}_p$ via $\mathbb{F}_2$, and Its Application for Computing the Hamming Distance of Linear Codes
This work addresses computational efficiency in coding theory, offering incremental improvements for researchers and practitioners in cryptography and error correction.
The paper tackles efficient arithmetic in finite fields F_p via binary operations, applying it to compute the minimum Hamming distance of linear codes over F_3 and F_7, with implementations in C that outperform state-of-the-art software like Magma and GAP/Guava on various processor types.
We present a new general method for performing basic arithmetic in the finite field~$\mathbb{F}_p$ for any prime $p>2$ by using traditional binary operations over~$\mathbb{F}_2$. Our new approach is efficient and competitive with current state-of-art methods. We apply our new arithmetic method to the computation of the minimum Hamming distance of random linear codes for the fields $\mathbb{F}_3$ and $\mathbb{F}_7$. Our new arithmetic method allows to apply new techniques such as the isometric addition that accelerate the computation of the Hamming distance. We have developed implementations in the C programming language for computing the Hamming distance that clearly outperform both state-of-art licensed software and open-source software such as \textsc{Magma} and \textsc{GAP}/\textsc{Guava} on single-core processors, multicore processors, and shared-memory multiprocessors.