Seven to the 256th Has 217 Digits and You Never Write One
Gepubliceerd op 27-10-2026 · 3 min leestijd · Dagelijkse calculators
Daniel Okonkwo — Front-enddeveloper en techredacteur bij OneKitly
Webprestaties · Bestandsformaten
Getoetst aan 2 bronnen
Seven raised to the 256th power is a number with 217 digits, and finding its remainder on division by thirteen requires computing none of them. The trick is that a remainder can be taken at every step: square seven to get 49, reduce to 10, square that to get 100, reduce to 9, and continue — eight squarings in total, because 256 is two to the eighth, and the answer is 9. The same method handles 2¹⁰⁰⁰ modulo 1,000,000,007 and returns 688,423,210 while the honest value has 302 digits. No intermediate number ever exceeds the square of the modulus, which is what makes the calculation possible on a machine with fixed-size integers.
7²⁵⁶ mod 13 is 9, and 2¹⁰⁰⁰ mod 1,000,000,007 is 688,423,210. Both come out of eight or ten squarings, with no number in the calculation ever exceeding the modulus squared.
Eight multiplications instead of two hundred and fifty-five
Computing a power by repeated multiplication takes one step per unit of exponent. Squaring instead doubles the exponent each time, so reaching 256 takes eight steps rather than 255, and reaching an exponent with three hundred digits takes about a thousand. An exponent that is not a power of two is handled by writing it in binary and squaring at every bit, multiplying in the base wherever the bit is set — which is why the method is often described as reading the exponent's binary digits from one end to the other. The cost is proportional to the number of bits in the exponent, not to the exponent itself.
Why the same eight steps take a constant time
Every intermediate value is reduced immediately, so it stays below the modulus and its square fits in twice the modulus's width. That bound is why the work per step does not grow as the exponent does, and why an implementation can size its arithmetic once and never revisit the question. It is also why the naive alternative fails so badly in practice: computing the 217-digit number first and reducing at the end is correct mathematically and needs arbitrary-precision arithmetic, several hundred bytes of memory per value, and a great deal more time than the whole modular calculation.
| Expression | Digits if written out | Result |
|---|---|---|
| 7²⁵⁶ mod 13 | 217 | 9 |
| 2¹⁰⁰⁰ mod 1,000,000,007 | 302 | 688,423,210 |
Veelgestelde vragen
- Why is 1,000,000,007 used so often as a modulus?
- Because it is prime, just under a billion, and its square fits inside a sixty-four-bit integer. Being prime means every non-zero value has a multiplicative inverse, so division works and nothing degenerates. Being just under a billion means results stay readable and collisions in a hash-like use are rare. Fitting its square in a machine word means an implementation can multiply two reduced values without overflow and without arbitrary-precision arithmetic. Those three properties together are the whole reason the number appears in competitive programming problems as often as it does.
- Does the timing of the calculation leak anything?
- It can, and that is a real class of attack rather than a theoretical worry. The naive version multiplies only where a bit of the exponent is set, so the running time depends on how many bits are set — and when the exponent is a private key, that is information leaving the machine through the clock. Implementations that matter therefore perform the multiplication unconditionally and discard the result when the bit is clear, paying a constant cost to make the timing independent of the secret. The same discipline shows up wherever a branch depends on private data.
Artikelen die je misschien interesseren
Alle gidsen →Vergelijkbare tools
Bronnen
Een fout in dit artikel gezien?