Open AccessEfficient Montgomery Modular Multiplication by using Residue Number System
Author(s) -
Elham Khani
Publication year - 2012
Publication title -
international journal of management and information technology
Language(s) - English
Resource type - Journals
ISSN - 2278-5612
DOI - 10.24297/ijmit.v2i1.1410
Subject(s) - residue number system , modular arithmetic , arithmetic , multiplication (music) , modular design , mathematics , elliptic curve cryptography , residue (chemistry) , binary number , computer science , cryptography , algorithm , public key cryptography , combinatorics , encryption , biochemistry , chemistry , operating system
Residue number system is a carry free system that performs arithmetic operation on residues instead of the weighted binary number. By applying Residue Number System (RNS) to Montgomery modular multiplication the delay of modular multiplication will be decreased. Modular multiplication over large number is frequently used in some application such as Elliptic Curve Cryptography, digital signal processing, and etc.By choosing appropriate RNS moduli sets the time consuming operation of multiplication can be replaced by smaller operations. In addition because of the property of RNS, arithmetic operations are done over smaller numbers called residues. In this paper by choosing appropriate moduli sets the efficiency of conversion from RNS to RNS that is the most time consuming part of the Montgomery modular multiplication will be increased.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom