Efficiency of SS ( l ) square-and-multiplyexponentiation algorithms
Kwok‐Yan Lam, Lucas C. K. Hui · Electronics Letters · 1994
SS(l) has been demonstrated experimentally to be the fastest square-and-multiply exponentiation scheme based on precomputation and string substitution. The Letter provides a complete proof of the efficiency of the SS(l) algorithm. It shows that SS(l) is a minimum weight representation scheme and proves that the expected weight of an n-bit SS(l)-represented exponent is n/(l+1) for large n.