Parallel exponentiation using common-multiplicand-multiplication and signed-digit-folding techniques

References

• Rivest , RL , Shamir , A and Adleman , L . (1978) . A method for obtaining digital signatures and public key cryptosystems . Commun. ACM , 21 ( 2 ) : 120 – 126 .
   Web of Science ®Google Scholar
• Montgomery , PL . (1985) . Modular multiplication without trial division . Math. Comput. , 44 ( 170 ) : 519 – 521 .
   Web of Science ®Google Scholar
• Koc , CK . (1995) . Analysis of sliding window techniques for exponentiation . Comp. Math. Appl. , 30 ( 10 ) : 17 – 24 .
   Google Scholar
• Yacobi Y (1990) Exponentiating faster with addition chains Proceedings of EUROCRYPT' 90, Advances in Cryptology, Springer-Verlag pp. 222–229
   Google Scholar
• Bos J Coster M (1990) Addition chain heuristics Proceedings of CRYPT' 89, Advances in Cryptology, Springer-Verlag pp. 400–407
   Google Scholar
• Knuth DE (1997) The Art of Computer Programming, Vol. II: Seminumerical Algorithms 3rd Edition, Addison-Wesley MA
   Google Scholar
• Premkumar , AB . (2002) . A formal framework for conversion from binary to residue numbers . IEEE Trans. Circuits Syst. II: Analog Digital Signal Processing , 49 ( 2 )
   Google Scholar
• Nozaki , H , Shimbo , A and Kawamura , S . (2003) . RNS Montgomery multiplicatiori algorithm for duplicate processing of base transformations . IEICE Trans. Fund. , E86-A ( 5 ) : 89 – 97 .
   Google Scholar
• Arno , S and Wheeler , FS . (1993) . Signed digit representations of minimal hamming weight . IEEE Trans. Comp. , 42 ( 8 ) : 1007 – 1010 .
   Web of Science ®Google Scholar
• Joye , M and Yen , S-M . (2000) . Optimal left-to-right binary signed-digit recoding . IEEE Trans. Comp. , 49 ( 7 ) : 740 – 748 .
   Web of Science ®Google Scholar
• Lou , D-C and Chang , C-C . (1996) . Fast exponentiation method obtained by folding the exponent in half . IEE Electron. Lett. , 32 ( 11 ) : 984 – 985 .
   Google Scholar
• Yen , S-M and Laih , C-S . (1993) . Common-multiplicand multiplication and its applications to public key cryptography . IEE Electronics Letters , 29 ( 17 ) : 1583 – 1584 .
   Web of Science ®Google Scholar
• Dimitrov , VS , Jullien , GA and Miller , WC . (2000) . Complexity and fast algorithms for multiexponentiations . IEEE Trans. Comp. , 49 ( 2 ) : 141 – 147 .
   Web of Science ®Google Scholar
• Gordon , DM . (1998) . A survey of fast exponentiation methods . J. Algorithms , 27 ( l ) : 129 – 146 .
   Google Scholar
• Nedjah N Mourelle LM (2002) Efficient parallel modular exponentiation algorithm Proceeding of ADVIS International Conference, Advances in Information Systems, Springer-Verlag pp. 405–414
   Google Scholar
• Diffie , W and Hellmen , E . (1976) . New directions in cryptography . IEEE Trans. Inform. 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 Trans. Inform. Theory , 31 ( 4 ) : 469 – 472 .
   Web of Science ®Google Scholar
• Koren I (2002) In: A. K. Peters (Ed.) Computer Arithmetic Algorithms 2nd Edition, Natick MA
   Google Scholar
• Avizienis , A . (1961) . Signed digit number representation for fast parallel arithmetic . IRE Trans. Electron. Comp. , EC-10 ( 3 ) : 389 – 400 .
   Google Scholar
• Shugang , W and Shimizu , K . (2002) . Residue signed-digit arithmetic circuit with a complement of modulus and the application to RSA encryption processor . Proceedings of the 9th IEEE International Conference on Electronics, Circuits and Systems , 2 : 591 – 594 .
   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 Trans. Inform. Syst. , E85-D ( 5 ) : 903 – 905 .
   Google Scholar
• Reitwiesner GW (1960) Binary arithmetic Advances in Computers 1 Academic Education Press New York 231 308
   Google Scholar
• Wu , T-C and Chang , Y-S . (1995) . Improved generalization common-multiplicand multiplications algorithm of Yen and Laih . IEE Electron. Lett. , 31 ( 20 ) : 1738 – 1739 .
   Web of Science ®Google Scholar
• Yen , S-M . (1997) . Improved common-multiplicand multiplication and fast exponentiation by exponent decomposition . IEICE Trans. Fund. , E80-A ( 6 ) : 1160 – 1163 .
   Google Scholar
• Takagi , N , Yoshiki , J and Takagi , K . (2001) . A fast algorithm for multiplicative inversion in GF(2 n ) using normal basis . IEEE Trans. Comp. , 50 ( 5 ) : 394 – 398 .
   Google Scholar
• Watanabe , Y , Takagi , N and Takagi , K . (2002) . A VLSI algorithm for division in GF(2 m ) based on extended binary GCD algorithm . IEICE Trans. Fund. , E85-A ( 5 ) : 994 – 999 .
   Google Scholar