Hello, I have the following problem:

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

Just in case: if the binary length of $\displaystyle e$ is $\displaystyle \ell$, using repeated squaring to compute $\displaystyle \alpha^e\pmod{n}$ uses at most $\displaystyle \ell$ squarings and $\displaystyle \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 $\displaystyle e_1$ is the smallest exponent, then we can look at $\displaystyle (\alpha_1\alpha_2\cdots \alpha_k)^{e_1} \alpha_2^{f_2}\cdots \alpha_k^{f_k}$, where $\displaystyle f_i=e_i-e_1$. Then we can precompute $\displaystyle \alpha_1\alpha_2\cdots \alpha_k$ at the cost of $\displaystyle k-1$ multiplications, then use repeated-squaring to raise it to the $\displaystyle e_1$, at the cost of (at worst) $\displaystyle \ell$ squarings and $\displaystyle \ell$ multiplications. However, the rest of the terms need to be computed via multiplication, which breaks the $\displaystyle 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.