TY - GEN
T1 - Fast modular reduction for large-integer multiplication for cryptosystem application
AU - Sreehari, Suhas
AU - Wu, Huapeng
AU - Ahmadi, Majid
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
KW - Barrett-based reduction
KW - Large integer modular reduction
KW - Mersenne primes
KW - Quasi-Mersenne primes
UR - http://www.scopus.com/inward/record.url?scp=84863702618&partnerID=8YFLogxK
U2 - 10.1109/DICTAP.2012.6215379
DO - 10.1109/DICTAP.2012.6215379
M3 - Conference contribution
AN - SCOPUS:84863702618
SN - 9781467307338
T3 - 2012 2nd International Conference on Digital Information and Communication Technology and its Applications, DICTAP 2012
SP - 226
EP - 229
BT - 2012 2nd International Conference on Digital Information and Communication Technology and its Applications, DICTAP 2012
T2 - 2012 2nd International Conference on Digital Information and Communication Technology and its Applications, DICTAP 2012
Y2 - 16 May 2012 through 18 May 2012
ER -