Application of New Classes of Mersenne Primes for Fast Modular Reduction for Large-Integer Multiplication

Abstract — This paper attempts to speed-up the modular reduction as an independent step of modular multiplication, which is the central operation in public-key cryptosystems. Based on the properties of Mersenne and Quasi-Mersenne primes, we have described four distinct sets of moduli which are responsible for converting the single-precision multiplication prevalent in many of today's techniques into an addition operation and a few simple shift operations. We propose a novel revision to the Modified Barrett algorithm presented in [3]. With the backing of the special moduli sets, the proposed algorithm is shown to outperform (speed-wise) the Modified Barrett algorithm by 80% for operands of length 700 bits, the least speed-up being around 70 % for smaller operands, in the range of around 100 bits. Keywords–Large integer modular reduction; Mersenne primes; Quasi-Mersenne primes; Barrett-based reduction. I