Simultaneous exponentiation by squaring ($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,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\ge 1$ 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.