Bit cost of modular exponentiation ($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 }_{2}m\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 givesThis 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.^[ref]

For ordinary integer powers with $|a|\ge 2$, 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.