• About
• Statistics
• Number Theory
• Java
• Data Structures
• Cornerstones
• Calculus

Fast Exponentiation

The idea behind fast exponentiation is a simple one. If we are trying to evaluate $a^k\pmod{m}$, we have two cases to consider.

Case 1

If $k$ is a power of $2$, we can find $a^k$ by successive squaring, reducing the numbers involved$\pmod{m}$ along the way to keep the magnitudes of the values we are dealing with reasonable.

For example, to find $7^{64}\pmod{13}$, we make the following calculations: $$\begin{array}{rclcl} 7^1&\equiv& 7\\ 7^2&\equiv& 49 &\equiv& 10\\ 7^4&\equiv& 100 &\equiv& 9\\ 7^8&\equiv& 81 &\equiv& 3\\ 7^{16}&\equiv& 9\\ 7^{32}&\equiv& 3\\ 7^{64}&\equiv& 9 \end{array}$$ Case 2

If $k$ is not a power of $2$, we can write it as a sum of powers of $2$ (i.e., its base 2 representation), find the related powers using the calculations suggested in Case 1 above, and then multiply the results together$\pmod{m}$.

For example, to find $7^{87}\pmod{13}$, we observe that: $$87 = 64 + 16 + 4 + 2 + 1$$ So, $$\begin{array}{rcl} 7^{87} &=& 7^{64} \cdot 7^{16} \cdot 7^4 \cdot 7^2 \cdot 7^1\\ &\equiv& 9 \cdot 9 \cdot 9 \cdot 10 \cdot 7\\ &\equiv& 729 \cdot 70\\ &\equiv& 1 \cdot 5\\ &\equiv& 5\pmod{13} \end{array}$$