= Bit cost of modular exponentiation
{title2=$O(\ell L^2)$}
The <binary powering multiplication count> counts <arithmetic operations>. The <time complexity> measured in operations on individual <bits> also depends on operand lengths. Put $L=\lfloor\log_2m\rfloor+1$, the binary length of the modulus, and let $\ell$ be the positive exponent's binary length. Stored residues use at most $L$ <bits>, and an unreduced product uses at most $2L$ <bits>.
With ordinary long <multiplication> and <division with remainder>, one modular product costs $O(L^2)$ operations on <bits>. Combining that cost with $O(\ell)$ modular products gives
$$
\text{bit cost of the powering loop}=O(\ell L^2).
$$
This bound includes reductions in the loop, and assumes the base has already been reduced and the exponent is available as a <binary expansion>. Reading the exponent takes $O(\ell)$ additional work; initial reduction of a very long base depends on its input length, and an inverse for a negative exponent adds further work. More generally, if a modular product costs $R(L)$ operations on <bits>, the powering loop costs $O(\ell R(L))$. Faster <multiplication> and reduction methods can improve the quadratic bound.<A Computational Introduction to Number Theory and Algebra by Victor Shoup>[Section 3.3.5, pp. 62–63, Theorem 3.3: operand-length costs; Section 3.4, p. 65: modular multiplication and powering bounds; Section 3.5, pp. 69–71: faster arithmetic]{ref}
For ordinary <integer> powers with $|a|\geq2$, the output itself has $\lfloor n\log_2|a|\rfloor+1$ <binary digits>. Even writing it takes work proportional to that length. Consequently $O(\log(n+1))$ <multiplications> does not imply $O(\log(n+1))$ operations on <bits>: the operands grow during ordinary <exponentiation by squaring>, whereas <modular exponentiation> keeps them bounded by the modulus. A squaring or multiplication by a small fixed base can also cost less than a general product, so equal counts need not mean equal running times.
Back to article page
