RAIRO-Theor. Inf. Appl.
Volume 49, Number 3, July-September 2015
|Page(s)||255 - 268|
|Published online||27 November 2015|
Algorithm design and theoretical analysis of a novel CMM modular exponentiation algorithm for large integers
Academic Center for Education, Culture and Research (ACECR),
Isfahan University of Technology (IUT) branch, Isfahan, Iran
2 Electrical and Computer Engineering Faculty, Semnan University, Semnan, Iran
Received: 16 May 2015
Accepted: 2 November 2015
Modular exponentiation is an important operation in public-key cryptography. The Common-Multiplicand-Multiplication (CMM) modular exponentiation is an efficient exponentiation algorithm. This paper presents a novel method for speeding up the CMM modular exponentiation algorithm based on a Modified Montgomery Modular Multiplication (M4) algorithm. The M4 algorithm uses a new multi bit scan-multi bit shift technique by employing a modified encoding algorithm. In the M4 algorithm, three operations (the zero chain multiplication, the required additions and the nonzero digit multiplication) are relaxed to a multi bit shift and one binary addition in only one clock cycle. Our computational complexity analysis shows that the average number of required multiplication steps (clock cycles) is considerably reduced in comparison with other CMM modular exponentiation algorithms.
Mathematics Subject Classification: 68P25 / 94A60 / 14G50 / 11Yxx / 11Y16 / 11Rxx
Key words: Modular multiplication / canonical recoding / modular exponentiation / public-key cryptosystem / high speed arithmetic
© EDP Sciences 2015
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.