Fast square-and-multiply exponentiation for RSA
Lucas C. K. Hui, K.Y. Lam · Electronics Letters · 1994
The authors describe a practical technique for improving the performance of square-and-multiply exponentiation. A family of linear time algorithms, denoted by SS(l) where l determines the maximum length of precomputed exponents, is presented. Analysis on n-bit exponents shows that the average number of multiplications required tends to n/(l + 1) for large n.