Calculation of products of powers using Modular Exponentiation

Question

I need to devise an algorithm that outputs $x^a * y^b$ (mod $m$) on an input of $m, x, y, a, b$ using the binary left to right modular exponentiation algorithm. It should be able to compute $x^{22} * y^{13}$ (mod $m$) using at most 4 multiplications and at most 4 squarings, after a precomputation of 1 multiplication.

If I were to compute both $x^{22}$ and $y^{13}$ separately and multiply them afterwards, I would use way too many multiplications and squarings. I think I need to find a way to somehow combine the computations for $x^{22}$ and $y^{13}$ but I don't know where to start at this point.

Can someone try to clarify this a bit for me?

Answer 1

I am omitting the modulo operations for clarity and name the product $c$. Precompute $xy,\;$ set $c=x,\;$ and perform the four squarings and multiplications:

$$c = c^2 y\longrightarrow c = x^2 y$$

$$c = c^2 xy\longrightarrow c = x^5y^3$$

$$c = c^2 x\longrightarrow c = x^{11}y^6$$

$$ c = c^2y\longrightarrow c = x^{22}y^{13}$$

Generally look at the bit representation of $a,b\;$ where some of the high bits of the smaller number may be zero. $$a = (a_n, a_{n-1}, \dots a_1, a_0)_2$$ $$b = (b_n, a_{n-1}, \dots b_1, b_0)_2$$ Now you can write down a left-to-right algorithm for computing $c= x^a y^b \pmod m$ in Pascal-like language

c := 1
z := x*y
for i=n downto 0 do begin
  c := c^2  mod m
  if (a[i]<>0) and (b[i]<>0) then c := c * z mod m
  else if a[i]<>0 then c := c * x mod m
  else if b[i]<>0 then c := c * y mod m
end;

Obviously $z=xy$ should be pre-computed.