= Simultaneous exponentiation by squaring
{title2=$p_j u_j^k=a_j^n$}
Several powers $a_j^n$ with the same <nonnegative integer> <exponent> $n$ can share one <exponentiation by squaring> loop. Initialize $p_j=1$, $u_j=a_j$ and $k=n$. The <loop invariants> are $p_j u_j^k=a_j^n$.
At each step, multiply every $p_j$ by $u_j$ if $k$ is an <odd integer>, then replace every $u_j$ by $u_j^2$ and $k$ by $\lfloor k/2\rfloor$. Indeed,
$$
p_j u_j^{k\bmod2}(u_j^2)^{\lfloor k/2\rfloor}=p_j u_j^k,
$$
so all invariants are preserved. The <loop variant> $k$ strictly decreases whenever it is positive. At $k=0$, the accumulators are exactly the requested powers. For $n=0$, no iteration is needed and every result is one.
For $r\geq1$ bases, the method uses $O(r\log(n+1))$ <multiplications> and $O(r)$ stored arithmetic values. These are arithmetic-operation counts; exact <integer> products can grow in bit length. For <modular exponentiation>, reducing each update <modulo> its intended <integer modulus> keeps the stored residues bounded. Sharing the exponent loop does not require mixing the bases' arithmetic types.
Back to article page
