Geodesic
Algorithm design and theoretical analysis of a novel CMM modular exponentiation algorithm for large integers
Rezai, Abdalhossein1 ; Keshavarzi, Parviz2
1 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
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 3, pp. 255-268

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2015007
Classification : 68P25, 94A60, 14G50, 11Yxx, 11Y16, 11Rxx
Keywords: Modular multiplication, canonical recoding, modular exponentiation, public-key cryptosystem, high speed arithmetic

Rezai, Abdalhossein 1 ; Keshavarzi, Parviz 2

1 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 
@article{ITA_2015__49_3_255_0,
     author = {Rezai, Abdalhossein and Keshavarzi, Parviz},
     title = {Algorithm design and theoretical analysis of a novel {CMM} modular exponentiation algorithm for large integers},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {255--268},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {3},
     year = {2015},
     doi = {10.1051/ita/2015007},
     mrnumber = {3434601},
     zbl = {1404.68211},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2015007/}
}
TY  - JOUR
AU  - Rezai, Abdalhossein
AU  - Keshavarzi, Parviz
TI  - Algorithm design and theoretical analysis of a novel CMM modular exponentiation algorithm for large integers
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2015
SP  - 255
EP  - 268
VL  - 49
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2015007/
DO  - 10.1051/ita/2015007
LA  - en
ID  - ITA_2015__49_3_255_0
ER  - 
%0 Journal Article
%A Rezai, Abdalhossein
%A Keshavarzi, Parviz
%T Algorithm design and theoretical analysis of a novel CMM modular exponentiation algorithm for large integers
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2015
%P 255-268
%V 49
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2015007/
%R 10.1051/ita/2015007
%G en
%F ITA_2015__49_3_255_0
Rezai, Abdalhossein; Keshavarzi, Parviz. Algorithm design and theoretical analysis of a novel CMM modular exponentiation algorithm for large integers. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 3, pp. 255-268. doi: 10.1051/ita/2015007

Cité par Sources :