Modular Arithmetic Based on Boolean Functions: A Divide and Conquer Approach

This paper introduces a new method for designing modular arithmetic units, for reduction (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">X</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">mod P</i>)), multiplication ((<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A · B</i>)(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">mod P</i>)), and multiplication by a constant ((<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">constant · A</i>)(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">mod P</i>)). 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.