0
$\begingroup$

Suppose $\mathbb{G}$ denotes a commutative group. Is there a way to the performance of an operation that does many modular exponentiations. That is an operation of the following type: suppose $b_1, \ldots, b_n \in \mathbb{G}$, $e_1, \ldots, e_n \in \mathbb{N}$, and suppose we want to compute $b_1^{e_1} \times b_2^{e_2} \times \ldots \times b_n^{e_n}$.

Is there a way to speedup this operation over a naive procedure that computes all the exponentiations first and multiplies them together?

  • 0
    corrected! thanks!2012-12-07

1 Answers 1

1

(note that I'm assuming we use the group abstractly; particular representations of the group may allow special techniques)

One easy rearrangement to do exponentiations "in bulk" would be to reorder the terms so that the $e_i$'s are a non-decreasing sequence, then compute

$ \prod_{i=1}^n \left( c_i \right)^{ e^i - e^{i-1} } \qquad \qquad \text{where } c_i = \prod_{j=i}^n b_i \qquad \qquad $

where I've adopted the convention that $e_0 = 0$. The $c_i$'s should be computed recursively. The products probably be computed from $n$ down to $1$. ( maybe you'll want to redo the algorithm starting with the ordering that the $e_i$'s are non-increasing)

In other words, you compute the product of everything raised to the smallest power that makes sense. The remaining products now have the same form, so you repeat. (i.e. throw out the factors that have already been exponentiated to the right amount, then exponentiate again to the next smallest)

Although the actual computation is probably better done in the opposite order than this intuitive justification expplains it.