Modular Exponentiation

Finds the remainder of a^b divided by m using repeated squaring. Because a^b is never formed in full, the exponent can be as large as you like. The number of digits a^b would have if written out is also shown.

Modular exponentiation is the remainder left when $a^b$ is divided by m. The obvious approach is to work out $a^b$ and then divide, but that falls apart as soon as the exponent grows. The default input $7^{128}$ is a 109-digit number, far beyond what an ordinary calculator can even display.

The remainder is still within reach, because of this property.

(x \times y) \bmod m = ((x \bmod m) \times (y \bmod m)) \bmod m

Multiplying first and then taking the remainder gives the same answer as taking remainders first and then multiplying. So if you take the remainder after every multiplication, the running value never grows beyond m. The 109-digit number never has to exist.

Avoiding 128 multiplications

Multiplying 128 times is still wasteful. Squaring repeatedly cuts the work dramatically.

$7^2 = 49$ , and 49 divided by 13 leaves 10
$7^4$ is the square of $7^2$ , so square 10 to get 100, which leaves 9
$7^8$ is the square of $7^4$ , so square 9 to get 81, which leaves 3
$7^{16}$ : square 3 to get 9, which leaves 9
$7^{32}$ : square 9 to get 81, which leaves 3
$7^{64}$ : square 3 to get 9, which leaves 9
$7^{128}$ : square 9 to get 81, which leaves 3

Seven squarings replaced 128 multiplications. The answer is 3.

128 happens to be 2 multiplied by itself seven times, so seven squarings landed exactly on it. When the exponent is not such a round number, write it in binary and multiply together the powers whose binary digit is 1. For $7^{10}$ , since 10 is 1010 in binary, you assemble $7^8 \times 7^2$ . The number of multiplications is at most twice the number of binary digits in the exponent.

Where it is used

Cryptography rests on this. RSA raises numbers of several hundred digits to enormous powers, over and over. Computing the power directly would outlast the universe, while repeated squaring finishes instantly. It also comes up when checking Fermat's little theorem, which says that if m is prime and a is not a multiple of m, then $a^{m-1}$ always leaves a remainder of 1 when divided by m.

Points to watch

With m set to 1, every remainder is 0, because everything divides evenly by 1. That includes the case $a^0 = 1$ , since 1 divided by 1 leaves nothing behind.

The digit count shows how long $a^b$ would be if written out in full, worked out from $b \times \log_{10} a$ . Read it as a sense of scale: the answer is smaller than m, while the number it came from is this enormous.