Exponent recoding and regular exponentiation algorithms

Abstract. This paper describes methods of recoding exponents to allow for regular implementations of m-ary exponentiation algorithms. Recod-ing algorithms previously proposed in the literature do not lend them-selves to being implemented in a regular manner, which is required if the implementation needs to resist side-channel attacks based on simple power analysis. The advantage of the algorithms proposed in this paper over previous work is that the recoding can be readily implemented in a regular manner. Recoding algorithms are proposed for exponentiation algorithms that use both signed and unsigned exponent digits