Hello, I have the following problem:

Suppose we are given \alpha_1, \alpha_2,\ldots, \alpha_k\in \mathbb{Z}_n and exponents e_1, e_2,\ldots, e_k where the binary length of the e_i is at most \ell. Show how to compute \beta:= \alpha_1^{e_1}\alpha_2^{e_2}\cdots \alpha_k^{e_k} using at most \ell squarings and \ell+2^k multiplications.

Just in case: if the binary length of e is \ell, using repeated squaring to compute \alpha^e\pmod{n} uses at most \ell squarings and \ell multiplications.

I tried a few things that makes the computation somewhat more efficient, but I am unable to stay within the multiplication bound. For example, if e_1 is the smallest exponent, then we can look at (\alpha_1\alpha_2\cdots \alpha_k)^{e_1} \alpha_2^{f_2}\cdots \alpha_k^{f_k}, where f_i=e_i-e_1. Then we can precompute \alpha_1\alpha_2\cdots \alpha_k at the cost of k-1 multiplications, then use repeated-squaring to raise it to the e_1, at the cost of (at worst) \ell squarings and \ell multiplications. However, the rest of the terms need to be computed via multiplication, which breaks the 2^k bound.

It is rather frustrating to have to read the author's mind to determine what kind of algorithm he was thinking of. So, I would appreciate any suggestions you might have about this problem.