Fast batch modular exponentiation with common-multiplicand multiplication

- An improved algorithm for batch exponentiation is proposed.
- Input exponents are divided into several groups.
- The algorithm produces several multiplications that share a common multiplicand.
- The computation cost is reduced by common-multiplicand Montgomery multiplication.
- The optimal values for exponent group sizes are analyzed.

We present an efficient algorithm for batch modular exponentiation which improves upon the previous generalized intersection method with respect to the cost of multiplications. The improvement is achieved by adopting an extended common-multiplicand multiplication technique that efficiently computes more than two multiplications at once. Our algorithm shows a better time-memory tradeoff compared to the previous generalized intersection method. We analyze the cost of multiplications and storage requirement, and show how to choose optimal algorithm parameters that minimize the cost of multiplications.