Technical Report TR-99-10, LCIS, National Central University, Taiwan, R.O.C., August, 1999.

Abstract. In this paper, a recently reported division chain based exponentiation algorithm by Walter is novelly extended into the multi-exponentiation case. The proposed algorithm is both simple and efficient which can be very useful for quite many modern public-key based cryptosystems. Detailed performance analysis and algorithm implementation are given.