Implementing Basic Arithmetic in ${\mathbb{F}}_p$ via ${\mathbb{F}}_2$, and Its Application for Computing the Hamming Distance of Linear Codes

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 $\text{textsc}Magma$ and $\text{textsc}GAP$/$\text{textsc}Guava$ on single-core processors, multicore processors, and shared-memory multiprocessors.