Improved batch exponentiation

An improved batch exponentiation algorithm is proposed that enhances the combination step of M'Raïhi–Naccache's batch exponentiation algorithm with a decremental combination strategy. In comparison with M'Raïhi–Naccache's algorithm for 160-bit and 1024-bit exponents, the proposed algorithm reduces the workload per exponentiation by about 15% in both cases when the optimal batch size is applied.