Clarification regarding multiple modular exponentiation

Question

If the base is same and exponents are different, for e.g. R1=b^x mod p; R2=b^y mod p; R3=b^z mod p; (p is large prime (2048 bit); x, y and z - 160 bit integers)) To calculate R1, R2 and R3 at the same time then my question is, is it takes around one exponentiation time or three exponentiations time? (I feel it is one exponentiation time) Pls clarify. Please suggest is there any method to compute R1, R2 and R3 efficiently?

Answer 1

The most efficient way to do this is to calculate $y^{2^n}$ for all $n\in \{0,\ldots, 160\}$. You'll then want to calculate the integers $n(i, j, k) = x^i \wedge y^j \wedge z^j$, where $i, j, k\in\{0, 1\}$ where $x^0 = x$ and $x^1 = \neg x$ and $\wedge$ is bitwise "and". Then, calculate $n(i, j, k)$ for all $(i, j, k)$ except $(1, 1, 1)$, by multiplying the correct $y^{2^n}$, and then $b^x = n(0, 1, 1) \cdot n(0, 0, 1) \cdot n(0, 1, 0) \cdot n(0, 0, 0) (\mod p)$, and similarly for $y$ and $z$.

This is about as efficiently as you can do this, and it will only be about $1$ exponentiation of work. Furthermore, if you're doing a lot of these, you should memoize the $y^{2^n}$, as that will cut the total work to exponentiate by about a third on average.

Answer 2

The term one exponentiation time is somewhat unclear. You should better count the modular multiplications, which are on the average $1.5 \log_2(x)$ for $b^x \pmod p$ etc if you use the binary square-and-multiply algorithm. Assume $x<y<z$ then compute $$R_1=b^x \pmod p,\quad R_2=R_1 \times b^{y-x} \pmod p,\quad R_3=R_2 \times b^{z-y} \pmod p$$ The time for all three $R_i$ will be roughly the same as for $R_3$ alone.