Technical Report TR-98-14, LCIS, Tamkang University, Taiwan, R.O.C., September 1998.

Abstract. This report considers the problem of finding a minimum-weighted representation of an integer under any modified radix-r number system. Contrary to existing methods, the proposed transformation is carried out from the left to the right (i.e., from the most significant position). This feature finds numerous applications and especially in fast arithmetic techniques because it reduces both time and space complexities. For example, applied to the elliptic curve exponentiation, the resulting algorithms are up to 11% faster than the right-to-left algorithms. This also yields the fastest known method to perform an exponentiation on an elliptic curve without precomputation, which is particularly attractive for small devices like the smart cards.