Fast exponentiation by folding the signed-digit exponent in half

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
• Montgomery , P. L. (1985) . Modular multiplication without trial division. . Mathematics of Computation , 44 ( 170 ) : 519 – 521 .
   Web of Science ®Google Scholar
• Yacobi Y. (1990) Exponentiating faster with addition chains. Proceedings of EUROCRYPT' 90 pp. 222–229
   Google Scholar
• Knuth D. E. (1997) The Art of Computer Programming: Seminumerical Algorithms II 3rd ed. Addison-Wesley MA
   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 Chang , C.-C. (1996) . Fast exponentiation method obtained by folding the exponent in half. . Electronics Letters , 32 ( 11 ) : 984 – 985 .
   Google Scholar
• Lou , D.-C. and Chang , C.-C. (1998) . A fast modular multiplication method. . International Journal of Computer Systems Science and Engineering , 13 ( 6 ) : 353 – 358 .
   Google Scholar
• Lou , D.-C. and Chang , C.-C. (1998) . An adaptive exponentiation method. . The Journal of Systems and Software , 42 ( 1 ) : 59 – 69 .
   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
• Chang , C.-C. and Lou , D.-C. (1997) . Parallel computation of the multi-exponentiation for cryptosystems. . International Journal of Computer Mathematics , 63 ( 1/2 ) : 9 – 26 .
   Google Scholar
• Gordon , D. M. (1998) . A survey of fast exponentiation methods. . Journal of Algorithms , 27 ( 1 ) : 129 – 146 .
   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 : 469 – 472 .
   Web of Science ®Google Scholar
• Boneh , D. (1999) . Twenty years of attacks on the RSA cryptosystem. . Notices of the AMS , 46 ( 2 ) : 203 – 213 .
   Google Scholar
• Stallings W. (1999) Cryptography and Network Security: Principles And Practice Prentice-Hall
   Google Scholar
• Yan S. Y. (2000) Number Theory for Computing 2nd ed. Springer-Verlag
   Google Scholar
• Koren I. (2002) Computer Arithmetic Algorithms 2nd ed., Peters, A.K.
   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
• Booth , A. D. (1951) . A signed binary multiplication technique. . Quarterly Journal Mechanics and Applied Mathematics , 4 : 236 – 240 .
   Web of Science ®Google Scholar
• Joye , M. and Yen , S.-M. (2000) . Optimal left-to-right binary signed-digit recoding. . IEEE Transactions on Computers , 49 ( 7 ) : 740 – 748 .
   Web of Science ®Google Scholar
• Dimitrov , V. S. , Jullien , G. A. and Miller , W. C. (2000) . Complexity and fast algorithms for multiplications. . IEEE Transactions on Computers , 49 ( 2 ) : 141 – 147 .
   Web of Science ®Google Scholar
• Hasan M. A. (2001) Efficient computation of multiplicative inverses for cryptographic applications. Proceedings of the 15th IEEE Symposium on Computer Arithmetic June 2001 pp. 66–72
   Google Scholar
• Takagi , N. , Yoshiki , J. and Takagi , K. (2001) . A fast algorithm for multiplicative inversion in GF(2n) using normal basis. . IEEE Transactions on Computers , 50 ( 5 ) : 394 – 398 .
   Google Scholar