Clarification regarding multiple modular exponentiation

Question

If the base is same and exponents are different, for example:

$R_1=b^x\bmod{p}$; $R_2=b^y\bmod{p}$; $R_3=b^z\bmod{p}$; ($p$ is large prime (2048 bit); $x$, $y$ and $z$ - 160 bit integers))

To calculate $R_1$, $R_2$ and $R_3$ at the same time, then my question is:

Does the calculation finish in around one exponentiation or three exponentiations? (I feel it is one exponentiation time)

Answer 1

Here's one approach that, assuming $x, y, z$ are random, takes approximately the same time as two exponentiations.

The general idea is to treat x, y, z as base 4 values, which we scan from the lsbit direction. We keep running values for $R1, R2, R3$, which are initially 1. At iteration $i$, we have the value $b^{4^i}$ and $b^{2 \cdot 4^i}$ (which takes two modular squarings to compute); if any of $x, y, z$ have a 3 in the digit $i$ position, we also compute the value $b^{3 \cdot 4^i}$ (this happens with probability 0.578, and takes one modular multiplication when it does). Then, for each of $x, y, z$, if their digit $d$ is not 0, then we multiply in $b^{d \cdot 4^i}$ into the corresponding $R$ value; for each variable, this takes one modular multiply with probability 0.75, for a total of 2.25 expected multiplies.

If we add everything up, we have 2 modular squarings, and 2.828 modular multiplications per step; for 160 bit exponents, there are 80 steps. If we remove one squaring (for the initial computation of $b^{4^0}$), and the 3 initial modular multiplications of $R1, R2, R3$, we get a total of 159 squarings, and 223 multiplications; this is in the same ballpark as twice the number of operations a good modular exponentiation for a 160 bit exponent would take.

I suspect that this isn't the best possible; it does show that some speed up can be achieved. On the other hand, I rather suspect that it'd be impossible to compute all three $R1, R2, R3$ in the same time that it takes to compute one of them; some slow down would appear to be inevitable.

Answer 2

One approach is to apply the algorithm of "exponentiation by squaring" simultaneously to the 3 exponents. One square mod p operation is common to the 3 exponents because the base is common. Then depending on the average numbers of 1 in the bitstring representation of each exponent, we can deduce an estimate in terms of number of modular multiplications (we can assume this is the most expensive operation in the algorithm).

Here is the algorithm applied to a single exponent (x : exponent, b : base, p : modulus)

r = 1
t = b
while (x > 0)
{
  if (x mod 2 == 1)
  {
    r = (r * t) mod p
  }
  x = x >> 1
  t = (t * t) mod p
}

Now if we combine the 3 exponents, and by assuming they have the same size in bits (to simplify) :

t = b
rx = 1
ry = 1
rz = 1
while ((x > 0) && (y > 0) && (z > 0))
{
  if (x mod 2 == 1)
  {
    rx = (rx * t) mod p
  }
  if (y mod 2 == 1)
  {
    ry = (ry * t) mod p
  }
  if (z mod 2 == 1)
  {
    rz = (rz * t) mod p
  }
  x = x >> 1
  y = y >> 1
  z = z >> 1
  t = (t * t) mod p
}

The cost of the entire operation strongly depends on the number of modular multiplications, which in turn depends on the number of "one" bits for each exponent ! Rough estimate : Let m be the exec time of one modular multiplication modulo p.

For one exponent, in average, the execution time is equal to 240 * m (160 times the second systematic square modulo p, plus 80 times the first modular multiplication). For 3 exponents, my estimate is : 400 * m ( (160 times, plus 3 * 80 times)).

Ratio : 400 / 240 = 1.66..