Fast exponentiation based on common-multiplicand-multiplication and minimal-signed-digit techniques

References

• Rivest , R. L. , Shamir , A. and Adleman , L. 1978 . A method for obtaining digital signatures and public key cryptosystems . Communications of the ACM , 21 ( 2 ) : 120 – 126 .
   Web of Science ®Google Scholar
• Diffie , W. and Hellmen , E. 1976 . New directions in cryptography . IEEE Transactions on Information Theory , 22 ( 6 ) : 644 – 654 .
   Web of Science ®Google Scholar
• ElGamal , T. 1985 . A public key cryptosystem and a signature scheme based on discrete logarithms . IEEE Transactions on Information Theory , 31 ( 4 ) : 469 – 472 .
   Web of Science ®Google Scholar
• Montgomery , P. L. 1985 . Modular multiplication without trial division . Mathematics of Computation , 44 ( 170 ) : 519 – 521 .
   Web of Science ®Google Scholar
• Knuth , D. E. 1997 . The Art of Computer Programming, Vol. II: Seminumerical Algorithms , 3rd , Massachusetts : Addison-Wesley .
   Google Scholar
• Yen , S.-M. and Laih , C.-S. 1993 . Common-multiplicand-multiplication and its applications to public key cryptography . Electronics Letters , 29 ( 17 ) : 1583 – 1584 .
   Web of Science ®Google Scholar
• Wu , T.-C. and Chang , Y.-S. 1995 . Improved generalization com-mon-multiplicand-multiplications algorithm of Yen and Laih . Electronics Letters , 31 ( 20 ) : 1738 – 1739 .
   Web of Science ®Google Scholar
• Shugang , W. , Shuangching , C. and Shimizu , K. 2002 . Fast modular multiplication using booth recoding based on signed-digit number arithmetic . IEEE Conference on APCCAS , 2 : 31 – 36 .
   Google Scholar
• Koc , C. K. and Johnson , S. 1994 . Multiplication of signed-digit numbers . Electronics Letters , 30 ( 11 ) : 840 – 841 .
   Web of Science ®Google Scholar
• Lou , D.-C. and Wu , C.-L. 2004 . Fast exponentiation by folding the signed-digit exponent in half . International Journal of Computer Mathematics , 81 ( 8 ) : 1187 – 1202 .
   Google Scholar
• Dimitrov , V. S. , Jullien , G. A. and Miller , W. C. 2000 . Complexity and fast algorithms for multiexponentiations . IEEE Transactions on Computers , 49 ( 2 ) : 141 – 147 .
   Web of Science ®Google Scholar
• Gordon , D. M. 1998 . A survey of fast exponentiation methods . Journal of Algorithms , 27 ( 1 ) : 129 – 146 .
   Web of Science ®Google Scholar
• Stallings , W. 2002 . Cryptography and Network Security: Principles and Practice , 3rd , New York : Prentice-Hall .
   Google Scholar
• Koren , I. 2002 . Computer Arithmetic Algorithms , 2nd , Natick, MA : A.K. Peters .
   Google Scholar
• Ha , J.-C. and Moon , S.-J. 1988 . A common–multiplicand method to the Montgomery algorithm for speeding up exponentiation . Information Processing Letters , 66 ( 2 ) : 105 – 107 .
   Google Scholar
• Avizienis , A. 1961 . Signed digit number representation for fast parallel arithmetic . IRE Transactions on Electronic Computers , EC–10 ( 3 ) : 389 – 400 .
   Google Scholar
• Syuto , M. , Satake , E. , Tanno , K. and Ishizuka , O. 2002 . A high–speed binary to residue converter using a signed–digit number representation . IEICE Transactions on Information and Systems , E85–D ( 5 ) : 903 – 905 .
   Google Scholar
• Reitwiesner , G. W. 1960 . Binary Arithmetic. Advances in Computers , New York : Academic Education Press .
   Google Scholar
• Arno , S. and Wheeler , F. 1993 . Signed digit representations of minimal Hamming weight . IEEE Transactions on Computers , 42 ( 8 ) : 1007 – 1010 .
   Web of Science ®Google Scholar
• Yen , S.-M. 1997 . Improved common-multiplicand-multiplication and fast exponentiation by exponent decomposition . IEICE Transactions on Fundamentals , E80–A ( 6 ) : 1160 – 1163 .
   Google Scholar
• Manochehri , K. and Pourmozafari , S. 2005 . Modified radix–2 Montgomery modular multiplication to make it faster and simpler . IEEE Conference on Information Technology: Coding and Computing (ITCC) , 1 : 598 – 602 .
   Google Scholar
• Wu , C.-L. , Lou , D.-C. and Chang , Te-Jen . 2005 . An efficient Montgomery exponentiation algorithm for cryptographic applications . Informatica , 16 ( 3 ) : 449 – 468 .
   Web of Science ®Google Scholar
• Tawalbeh , L. A. , Tenca , A. F. and Koc , C. K. 2005 . A radix–4 scalable design . IEEE Potentials , 24 ( 2 ) : 16 – 18 .
   Google Scholar
• Fournaris , A. P. and Koufopavlou , O. 2005 . A new RSA encryption architecture and hardware implementation based on optimized Montgomery multiplication . IEEE Symposium on Circuits and Systems (ISCAS) , 5 : 4645 – 4648 .
   Google Scholar