Fast modular reduction for large-integer multiplication for cryptosystem application
Suhas Sreehari, Huapeng Wu, Majid Ahmadi · 2012
In this paper, we attempt to speedup 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 revision to the Modified Barrett algorithm presented in [3]. With the backing of the special moduli sets, our proposed algorithm is shown to outperform the Modified Barrett algorithm by nearly 25% when we consider the level of reduction (which bears a direct effect upon the speed of the second phase of reduction), and by over 10% when we consider the time taken for reduction.