Modular Arithmetic Based on Boolean Functions: A Divide and Conquer Approach
Danila Gorodecky, Leonel A. Sousa · IEEE Access · 2025
This paper introduces a new method for designing modular arithmetic units, for reduction (X(mod P)), multiplication ((A · B)(mod P)), and multiplication by a constant ((constant · A)(mod P)). The proposed method follows a divide and conquer approach by sub-vector splitting at the first stage, and merging the results in a second stage. A framework that automates the process has been developed. Experimental results automatically obtained by implementing modular arithmetic with the proposed approaches on reconfigurable devices (FPGAs). Experimental results show that our approach outperforms standard FPGA design tools by up to 30x in area efficiency (LUTs) and up to 2.9x in speed for inputs up to 500 bits.