Try to compute 3^{1{,}000{,}000} \bmod 7 the obvious way — multiply by 3 a million times, reducing at the end — and you'll be sitting there long after the sun burns out. A computer isn't fast enough to save you either: a million multiplications of gigantic numbers is still a lot of work.

And yet there's a trick that gets the exact same answer in about twenty steps. It's called square-and-multiply (or repeated squaring), and it's not a curiosity — it's the single piece of arithmetic that makes modern cryptography computationally possible at all. Every time your browser sets up a secure connection, a chip somewhere is running this exact algorithm on numbers hundreds of digits long, and finishing before you'd notice the delay.

Systems like RSA are built entirely out of computations that look like m^{e} \bmod n, where m is a message, e is a key, and n is a large product of primes. If raising a number to a power took time proportional to the exponent, none of this would work — the keys involved are chosen precisely because they're huge, which is what keeps an eavesdropper from guessing them. The only reason huge exponents are usable at all is that square-and-multiply turns "proportional to the exponent" into "proportional to the number of digits of the exponent" — a difference that, at cryptographic scale, is the difference between milliseconds and forever.

The 20 steps for a million-sized exponent isn't a rough guess pulled out of thin air: 2^{20} = 1{,}048{,}576, which is just over a million, so an exponent that size needs about 20 bits to write in binary — and, as you'll see below, that's exactly how many squarings the algorithm needs.

The trick: double the exponent, don't count up to it

The slow way climbs the exponent one step at a time: m, m^2, m^3, m^4, \ldots — reaching m^{e} costs e - 1 multiplications. The fast way climbs by squaring, which doubles the exponent at every step instead of just adding one to it:

After only k squarings you already hold m^{2^k} — exponent 2^{20}, over a million, needs just 20 squarings. But most exponents aren't neat powers of two. The fix is to write the exponent e in binary, which is exactly a sum of powers of two, and then combine only the squarings you need:

That's the whole algorithm: about \log_2 e squarings, plus one extra multiplication for each 1-bit of e.

Why does writing e in binary help? Because binary is exactly the statement "every whole number is a sum of distinct powers of two, in exactly one way" — the same fact behind a classic weighing puzzle: with just one weight each of 1, 2, 4, 8, 16, \ldots grams, you can balance any whole number of grams by choosing which weights to use. Here the "weights" are the squarings m^1, m^2, m^4, m^8, \ldots, and the bits of e tell you which ones to place on the scale. In computer-science terms, the running time has gone from O(e) — proportional to the exponent itself — down to O(\log e) — proportional to its number of digits.

Worked example: tracing $3^{13} \bmod 7$ step by step

First, 13 in binary is 1101_2 = 8 + 4 + 1, i.e. the bits (left to right) are 1, 1, 0, 1. Start the running result at 1 and process each bit, reducing mod 7 every time:

• Bit 1 (value 1): square 1^2 = 1; the bit is 1, so multiply by 3: 1 \times 3 = 3. Running result: 3.
• Bit 2 (value 1): square 3^2 = 9 \equiv 2 \pmod 7; bit is 1, so multiply by 3: 2 \times 3 = 6. Running result: 6.
• Bit 3 (value 0): square 6^2 = 36 \equiv 1 \pmod 7; bit is 0, no multiply. Running result: 1.
• Bit 4 (value 1): square 1^2 = 1; bit is 1, so multiply by 3: 1 \times 3 = 3. Running result: 3.

Done: 3^{13} \equiv 3 \pmod 7. That took four squarings and three extra multiplications — seven small modular multiplications in total, instead of the twelve a naive climb (13 - 1) would need. Every intermediate value along the way stayed a single digit — nothing ever got bigger than 36.

A second example, the other way round

You can also build the powers-of-two table first and multiply in the pieces afterwards — the same idea, organised right-to-left. For 7^{13} \bmod 11, with 13 = 8 + 4 + 1:

Same ingredients — repeated squaring plus picking out the bits that are 1 — just assembled in a different order. Whichever way you organise the bookkeeping, the number of modular multiplications stays around \log_2 e.

This "table of squarings, then multiply in the right ones" style is handy when you're working by hand, since you can compute the whole table first and then simply pick out which entries to multiply. The left-to-right version from the previous example is what a computer actually runs, because it needs to keep only one running number in memory rather than a whole table of powers — a small but real saving when the numbers involved are hundreds of digits long.

Just how big is the speed-up?

The naive method needs e - 1 multiplications; square-and-multiply needs roughly 2\log_2 e (the squarings, plus at most as many multiplications for the 1-bits). The gap explodes as e grows:

• e = 13: naive 12 vs. fast 7 — a modest saving.
• e = 1{,}000{,}000: naive 999{,}999 vs. fast around 40 — thousands of times fewer steps.
• e a 2048-bit RSA exponent: naive would need 2^{2048} multiplications — vastly more than the number of atoms in the observable universe — while fast needs only a few thousand, done in milliseconds.

This single efficient algorithm is what makes Fermat's little theorem, Diffie–Hellman key exchange, RSA, and primality testing all usable in practice rather than just in theory.

Here it is as code — the whole algorithm fits in a dozen lines, and it's a piece of arithmetic old enough to predate computers by millennia: versions of "square repeatedly, multiply in the marked steps" show up in ancient Indian and Egyptian mathematics, long before anyone had a use for it in secret messages sent over wires. Run it below and watch it return 3^{1{,}000{,}000} \bmod 7 instantly.

Putting it together

The whole idea rests on three small observations stacked on top of one another: squaring doubles an exponent instead of just incrementing it; any exponent can be built by adding together powers of two, because that's what its binary representation is; and reducing modulo n at every single step keeps every number involved small, however colossal the final exponent gets. Individually, none of the three is a deep idea — but combined, they turn a computation that should be impossible into one that finishes before you can blink.