Hybrid method for modular exponentiation with precomputation

Abstract

The authors present a new hybrid method for perfonming modular exponentiation using a hybrid ternary-quinary number system. A recent result concerning performing modular exponentiation with precomputation was presented by Dimitrov and Cooklev: their average number of modular multiplications is 0.3381n, where n is the length of the modulus, while the authors' proposed method only needs 0.3246n modular multiplications. Furthermore, compared to Dimitrov and Cooklev's approach, the authors' method reduces the amount of storage by 56.8% if the modulus is a 512 bit number.