A Parallel Modular Exponentiation Scheme for Transformed Exponents

This paper introduces an efficient method to compute modular exponentiation operations in parallel. For the parallel process of a modular exponentiation operation, the exponent is transformed into mixed radix digits first. Each digit is then an exponent for a partial result of the modular exponentiation operation. Because the computing processes for these partial results are highly independent, they can be carried out concurrently. The bases in these partial exponentiation operations can be pre-computed and used till the exponent moduli set changed. If the largest mixed radix digit is

k

-bits with respect to

m

exponent moduli, the time complexity for the proposed scheme is then

k

+

log

2

m

. The performing complexity is very efficient, compared with other methods. Since the comparison is based on the same modular multiplication hardware, the performance is better if the fewer operations required. In the scenario of two exponent moduli, the performance improvment is approximately 40%. Finally, the proposed scheme is presented with a parallel algorithm for which the computing architecture is also illustrated in the paper.