Extension and implementation of the mod without mod algorithm to efficiently compute the modulus of a number in hardware

Abstract

This thesis discusses a hardware implementation of modulo that does not require a multiplication. This implementation is based on the algorithm proposed in Mark A. Will's "Mod without mod" in which the an algorithm is presented to calculate the modulus of large values using shifting and adding. This allows our implementation to be comparable in clock cycles to other implementations without the need for a multiplier's delay. This algorithm is compared with others, such as Barret reduction, Montgomery reduction, and fast modular reduction. Our implementation of this modulo algorithm is shown to be faster in many cases. This paper proposes both a hardware implementation of this algorithm as well as synthesis results in soi12s0 45nm IBM Multi-threshold CMOS (MTCMOS) technology and ARM-based standard cells.