= Modular exponentiation
{title2=$a^b\bmod m$}
= Modular power
{synonym}
Modular exponentiation computes the <remainder> $a^n\bmod m$ for an <integer> base $a$, a <nonnegative integer> exponent $n$, and, here, an <integer> modulus $m\geq2$. It applies <exponentiation by squaring> while reducing after \b[each] <multiplication>, including each squaring. The result is the unique representative in $\{0,\ldots,m-1\}$. There is no requirement that the base be <coprime> to the modulus when the exponent is nonnegative.<A Computational Introduction to Number Theory and Algebra by Victor Shoup>[Section 3.4, pp. 64–66: canonical representatives, modular products, and nonnegative-exponent repeated squaring]{ref}
Take $a=2$, $n=13=(1101)_2$, and $m=17$. Initialize $r=2$; the remaining digits give
$$
\begin{aligned}
11&:\quad 2^2\bmod17=4,\quad4\cdot2\bmod17=8,\\
110&:\quad 8^2\bmod17=64\bmod17=13,\\
1101&:\quad13^2\bmod17=169\bmod17=16,\quad16\cdot2\bmod17=15.
\end{aligned}
$$
Hence \b[$2^{13}\bmod17=15$]. The final operation multiplies $16$ by $2$, since the preceding square has already been reduced. The computation never needs to construct $2^{13}=8192$.
In general reduce the base first, $x=a\bmod m$. For $n>0$, initialize $r=x$ and process the remaining <binary digits> with $r\leftarrow r^2\bmod m$, followed, for a digit one, by $r\leftarrow rx\bmod m$. The <loop invariant> is
$$
0\leq r<m,\qquad r\equiv a^p\pmod m,
$$
where $p$ is the processed prefix value. The congruence is preserved because <modular arithmetic> respects <multiplication>: if $u\equiv v\pmod m$, then $u^2\equiv v^2$ and $ux\equiv va\pmod m$. Thus changing representatives never changes the final <congruence class>.
Both factors in every product are less than $m$, so the unreduced product is less than $m^2$, and the stored result is again less than $m$. The same bounds hold for a gigantic exponent, such as $n=2^{1000}$: there are $1000$ squarings, each on bounded-size residues. For base two, the corresponding ordinary power would have $2^{1000}+1$ <binary digits>. The benefit is avoiding the huge ordinary power altogether, rather than constructing it and taking one final <remainder>. Initial reduction is essential when the supplied base is much larger than the modulus.
For $n=0$, return $1$ under the same empty-product convention as <exponentiation by squaring>. For $n=-k<0$, require $\gcd(a,m)=1$, find the <modular multiplicative inverse> $a^{-1}\bmod m$, and compute $(a^{-1})^k\bmod m$; the <extended Euclidean algorithm> can find that inverse. Its cost is separate from the positive-exponent <binary powering multiplication count>. For example, $2^{-1}\equiv9\pmod{17}$, while $2^{-1}\bmod4$ is undefined because $2$ and $4$ are not <coprime>.
A <reversible computation> gives the coherent <quantum modular exponentiation> used in <quantum order finding> and <discrete-logarithm Fourier sampling>.
Back to article page
