Exploring Generalization of Shoup Modular Multiplier

Shoup's modular multiplication algorithm follows the idea of Barrett reduction algorithm. While Barrett reduction can be used to multiply two arbitrary numbers, Shoup's multiplier requires a pre-computed value for one of the operands. At the same time, Shoup is more efficient as it requires less computation. In this work, we extend Shoup's multiplier by adding functionality to operate on arbitrary operands in such a way that the multiplier can be used in both ways: using the original Shoup algorithm when one of the arguments can be pre-computed, or a general multiplier. The general multiplier reuses Shoup functionality in its core. We compare the performance of the multipliers in a software simulator and a hardware design.