Title: APPLICATION OF NEW CLASSES OF MERSENNE PRIMES FOR FAST MODULAR REDUCTION FOR LARGE-INTEGER MULTIPLICATION

Issue Number: Vol. 1, No. 1
Year of Publication: Aug - 2012
Page Numbers: 15-19
Authors: Suhas Sreehari, Huapeng Wu, Majid Ahmadi
Journal Name: International Journal of Cyber-Security and Digital Forensics (IJCSDF)
- Hong Kong

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.