45Strings & number theory — the crypto and quant layer

In Chapter 44 we turned almost every hard problem into dots and lines, and we walked the graph three ways. Here we pick up two toolkits that punch far above their weight, and it turns out they share one instinct. String search is how spell-check, git diff, DNA aligners and Ctrl-F find a needle in a haystack. The whole trick is refusing to re-read what you already know. Number theory is the quiet machinery under every padlock icon in your browser. It runs on primes, remainders, and one calculation that is trivial to run forward and effectively impossible to run backward. The one question we keep asking both halves is the thing that actually matters. Is there a direction that's cheap and a reverse that's expensive, and can I stop paying twice for the same work? By the end you'll derive why the naive scan is slow and how to fix it. You'll sieve every prime up to a million by pure elimination, then raise a number to the millionth power in about twenty multiplications. And you'll see exactly why a TLS handshake is safe.

01The naive scan re-reads what it already knows

Let's start with the most honest version of the problem. You've got a short pattern and you want to find it inside a long text. Watch the obvious method run: line the pattern up at position 0 and compare character by character. On a mismatch, shift the pattern one step right and start comparing again from scratch. It works, and it always finds the match, so the only open question is what it costs. We answer that the way we always do: we count the operations, we don't guess (chapter 31).

Let the text be length n and the pattern length m. At each of the n − m + 1 starting positions we might compare up to m characters. Multiply those together and the worst case is (n − m + 1) · m comparisons, which is O(n·m). The friendly case looks fine: searching "cat" in "the cat sat on the mat" takes just 22 comparisons, because most alignments fail on the very first letter. The trap is text that almost matches everywhere.

def naive_search(text, pat):
    n, m = len(text), len(pat)
    comps = 0
    for i in range(n - m + 1):        # every start position
        j = 0
        while j < m:                  # compare pattern left to right
            comps += 1
            if text[i+j] != pat[j]:
                break                 # mismatch: give up, shift by 1
            j += 1
    return comps

print(naive_search("aaaaaaaaaaaaaaaaaaaab", "aaaab"))  # 85
print(naive_search("the cat sat on the mat", "cat"))    # 22

Line 4 walks every start position, and line 6 compares until a mismatch. Feed it the pathological string "a"×20 + "b" with the pattern "aaaab" and the cost is 85 comparisons (verified). At each of 17 positions it matches four as, fails on the b, and throws all four matches away. Push it to a 10,001-character run with a length-100 pattern and the count explodes to 990,200. The waste has a name, and naming it is the engineer's move (chapter 35): we keep re-reading text characters we already looked at.

Let's check that 990,200 by hand, because a number you can re-derive is a number you own. The text is 10,001 characters and the pattern is 100, so there are 10,001 − 100 + 1 = 9,902 starting positions. At each one the scan matches a run of 99 as and then reads one more character, so every position costs 100 comparisons. Multiply them and you land exactly on it: 9,902 × 100 = 990,200. Now notice what that arithmetic is really saying. Almost every comparison lands on a text character the scan already read at an earlier position. The text is only 10,001 characters long, yet on average we touched each character nearly a hundred times. That repeated touching is the whole disease, and the next two sections are two different cures.

If we already matched four as, we know the next window starts with three as. Why look again →

02KMP: never re-examine a matched character

Here is the insight that Knuth, Morris and Pratt turned into an algorithm around 1970, and you can feel it before you see any machinery. When the pattern aaaab matches four as and then fails on the b, those four matched characters are not garbage — they are information. They tell you the text right here is aaaa…, so the next plausible alignment already has three as satisfied for free. So there is no reason to ever walk the text pointer backwards. None.

KMP precomputes, from the pattern alone, a small table that answers one question. If I fail after matching k characters, how many are still guaranteed to match at the next useful shift? That table lets the text pointer march forward and never retreat, so each text character is looked at essentially once. The whole search is O(n + m): the n to scan the text plus the m to build the table. Linear — the nested loop collapses into a single pass.

# same haystack and needle as before, counting TEXT-character reads
naive : 85 reads     KMP : 21 reads     (text length = 21)
naive : 990,200      KMP : 10,001       (text length = 10,001)

# the pattern's "memory" table (how much prefix survives a mismatch)
lps("aaaab") == [0, 1, 2, 3, 0]
lps("abcab") == [0, 0, 0, 1, 2]

Those numbers are measured, not asserted. KMP reads each of the 21 text characters exactly once, while the naive scan read 85. On the big string it is 10,001 versus 990,200, and that gap widens forever as the text grows. The lps table is the pattern's self-knowledge: for aaaab, after matching aaaa we can keep 3 characters on the next shift. That [0,1,2,3,0] is the "don't look back" rule, baked in ahead of time.

Let's read [0,1,2,3,0] slot by slot, because the table looks more cryptic than it is. Slot k asks one question about the first k+1 pattern characters: how long is the longest chunk that is both a prefix of the pattern and a suffix of what just matched? For aaaa the answer is 3, because aaa sits at the start and also at the end. That overlap is exactly the part you never have to re-check after a shift. The last slot is 0 because anything ending in b can't match the all-a opening of the pattern. Look back at the figure and watch the pattern jump by exactly these amounts. The table costs O(m) to build from the pattern alone, and it pays for itself on the very first mismatch.

03Rabin-Karp: slide a hash over the text

Rabin-Karp fights the same enemy, re-work, with a different idea: don't compare characters, fingerprint them. Turn every length-m chunk of text into a single number, a hash (chapter 37), and turn the pattern into a number too. If the two numbers differ, the chunks differ, so you skip the comparison entirely. But there's a catch: computing a fresh hash for every window would itself be O(m) per window, O(n·m) total, which is no win at all. The move that saves it is a rolling hash: when the window slides one step, don't recompute — update. Subtract the character leaving on the left, shift, and add the character entering on the right. That's O(1) per slide, O(n) for the whole text.

Think of the window's hash as a number written in base 256, with one digit per byte. Sliding right is exactly like turning 734 into 345. Drop the leading digit's place value, multiply what's left by the base, then add the new trailing digit. Do all of it modulo a big prime so the number stays small.

Run the decimal version with real numbers, so the move becomes yours. Start with 734 and slide the window right, where the incoming digit is 5. Drop the leading 7's place value first: 734 − 7×100 = 34. Shift what's left one place and add the newcomer: 34 × 10 = 340, then 340 + 5 = 345. Three operations, and none of them cared how wide the window was. The base-256 version is the same three steps with 256 standing in for 10, taken mod a large prime at every stage. That modulus is not decoration. Without it, a 100-character window would be an integer around 240 digits long, and every "cheap" update would turn into slow big-number arithmetic.

BASE, MOD = 256, 1_000_000_007
high = pow(BASE, m-1, MOD)             # place value of the leftmost char
h = hash_of(text[:m])                  # hash of the first window
# slide from window i to i+1 in O(1):
h = ((h - ord(text[i])*high) * BASE + ord(text[i+m])) % MOD
#     - drop the leaving char --  -shift-  - add the entering char -

Ran on "the cat sat on the mat" searching "cat", the pattern hashes to 6513012 and the window slides 19 times. Here is the honesty check: every single rolling update was compared against a hash computed from scratch, and every one matched exactly. The match is reported at index 4, the same spot the naive scan found. Sometimes a hash collides, meaning two different chunks share the same fingerprint. When that happens you fall back to a direct character check, so a collision costs a little time but never a wrong answer.

String search leaned on hashing and modular arithmetic — mod a big prime. That "mod" is the doorway to number theory, and it starts with the oldest algorithm still in daily use →

04Euclid and clock arithmetic

Modular arithmetic is clock math: on a 12-hour clock, 10 + 5 = 3, because the hand wraps around after 12. Written as a formula, that's 15 mod 12 = 3, and that wrap-around is the entire foundation of what follows. Cryptography computes with remainders, not full numbers, because remainders stay small and they hide information.

Here's why I said remainders hide information, because that phrase is doing real work. On the clock, 15 hours lands on 3, but so does 27, and so does 39. Check it yourself: 27 mod 12 = 3 and 39 mod 12 = 3, since 24 and 36 are full turns of the dial. So if I show you only the 3, you cannot recover which of infinitely many starting numbers produced it. The wrap-around destroys exactly the piece an attacker would need to work backwards. That is the shape cryptography wants: an operation easy to perform and lossy to reverse. Keep the clock in your head for the rest of the chapter. Every mod from here on is that same dial wrapping, just with a giant prime where the 12 was.

The greatest common divisor (GCD) of two numbers is the largest number dividing both. The naive way is to test every candidate down from the smaller number, which costs O(min(a,b)). Euclid's insight, over two thousand years old and still unbeaten, is one line: any divisor of a and b also divides their remainder a mod b. So replace the bigger number with that remainder, and repeat. The numbers shrink fast, and when one hits zero the other is your answer. You stepped this in trace T33 — here's why it's fast.

Why must Euclid's one line be true? Write the division out: a mod b is just a − q·b, where q counts how many whole times b fits into a. If some number d divides both a and b, then it divides q·b, so it also divides the difference a − q·b. That is the entire proof: no common divisor is ever lost when we swap in the remainder. Watch it run on gcd(48, 18). First, 48 mod 18 = 12, so the pair becomes (18, 12). Then 18 mod 12 = 6, giving (12, 6). Then 12 mod 6 = 0, and we stop: the answer is 6. Check it against the definition: 48 = 6 × 8, 18 = 6 × 3, and nothing larger divides both. Three remainder steps replaced up to 18 trial divisions.

def gcd(a, b):
    while b:                 # until nothing is left over
        a, b = b, a % b      # shrink: replace (a,b) with (b, remainder)
    return a

gcd(1071, 462)      # 21, reached in 3 steps
gcd(832040, 514229) # 1,  worst case: 28 steps (consecutive Fibonacci numbers)

Line 3 is the whole algorithm: each step throws away the larger number entirely and keeps only the remainder. How fast do the numbers shrink? Every two steps at least halves the larger value, so the step count is O(log(min(a,b))) — logarithmic, like binary search (the growth zoo, chapter 32). The measured worst case is telling: feed it two consecutive Fibonacci numbers and every step peels off exactly one, so gcd(832040, 514229) takes 28 steps. Fibonacci is the slowest possible input, and even that is tiny. Python's built-in math.gcd runs this same idea.

you type
$ python numbertheory_idiom.py

import math

# ---------- 1. gcd / lcm — variadic since 3.9 ----------
print(math.gcd(1071, 462), math.gcd(48, 18), math.gcd(12, 18, 30), math.gcd(0, 0))
print(math.lcm(4, 6), math.lcm(3, 4, 5))

# ---------- 2. the clock: Python's % follows the sign of the DIVISOR ----------
print(15 % 12, 27 % 12, -7 % 12, 7 % -12)
print(divmod(15, 12), divmod(-7, 12), divmod(-7, 3))

# ---------- 3. three-argument pow = the square-and-multiply engine ----------
print(pow(7, 13, 11), 7 ** 13 % 11)
print(pow(2, 1_000_000, 10**9 + 7))

# ---------- 4. pow(a, -1, m) IS the modular inverse (3.8+) ----------
e, phi = 17, 3120
d = pow(e, -1, phi)
print(d, (e * d) % phi, divmod(e * d, phi))

# ---------- 5. the whole of RSA, in four lines ----------
p, q = 61, 53
n, phi = p * q, (p - 1) * (q - 1)
e = 17
d = pow(e, -1, phi)
c = pow(65, e, n)
print(n, phi, d, c, pow(c, d, n))

# ---------- 6. what happens when the inverse does not exist ----------
try:
    pow(6, -1, 12)
except ValueError as err:
    print("ValueError:", err)
print(math.gcd(6, 12))

# ---------- 7. isqrt is exact; the float square root is not ----------
big = 10**18 - 1
print(math.isqrt(big), int(big ** 0.5))
print(math.isqrt(big) ** 2 <= big, int(big ** 0.5) ** 2 <= big)

you see
21 6 6 0
12 60
3 3 5 -5
(1, 3) (-1, 5) (-3, 2)
2 2
235042059
2753 1 (15, 1)
3233 3120 2753 2790 65
ValueError: base is not invertible for the given modulus
6
999999999 1000000000
True False

Remainders let us tame huge numbers. The next tool uses nothing but a wrap-around and a crossing-out pencil to find every prime there is →

05The Sieve of Eratosthenes — primes from pure elimination

A prime is a number with no divisors but 1 and itself — the atoms of arithmetic, and the raw material of crypto. To find every prime up to n, you could test each number for primality one at a time. Eratosthenes, a librarian in ancient Alexandria, had a lazier and faster idea: don't hunt for primes — eliminate non-primes. Write every number from 2 to n. Take 2, keep it, and cross out every multiple of 2. Move to the next number still standing (3), keep it, cross out every multiple of 3. The next survivor (5), same. Whatever is never crossed out is prime, because a composite number is by definition a multiple of some smaller prime.

Before trusting any code, run the sieve by hand up to 30 — it takes under a minute. Take 2 and cross out 4, 6, 8, and every even number up to 30. The next survivor is 3, so cross out its remaining multiples: 9, 15, 21, 27 (the even ones are already gone). The survivor after that is 5, and its first useful strike is 5² = 25. Then comes 7, but 7² = 49 is past 30, so the sweep is done. Left standing: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — ten primes, and you never tested a single number for primality. Every survivor must be prime, because any composite up to 30 is a multiple of 2, 3, or 5, and those multiples are all gone. That one-minute sweep is exactly what the code does, a million numbers wide.

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:                 # stop at √n — see below
        if is_prime[p]:
            for k in range(p*p, n+1, p):  # cross out p², p²+p, p²+2p, …
                is_prime[k] = False
        p += 1
    return [i for i in range(n+1) if is_prime[i]]

sieve(30)   # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Two small optimizations carry real weight. Line 5 stops at √n, because any composite ≤ n has a factor no larger than its square root. So once you've sieved with primes up to √n, everything left standing is prime. Line 7 starts crossing at p² instead of 2p, because smaller multiples of p (like 2p, 3p) were already crossed by smaller primes. The cost is startling: O(n log log n), and log log n stays under 4 for any n you'll ever sieve. Measured: π(1,000,000) = 78,498 primes, found in one sweep.

06Fast modular exponentiation — the engine of crypto

Cryptography constantly computes a^b mod m where a, b, and m are numbers hundreds of digits long. Compute a^b the obvious way — multiply a by itself b times — and you'd need b − 1 multiplications, and the intermediate number would have billions of digits. Both are fatal. Two ideas fix it. First, reduce mod m after every multiply, so the number never grows past m. Second, square, don't multiply one-by-one — the divide-and-conquer trick from chapter 36. To get a^13, write 13 in binary as 1101: a^13 = a^8 · a^4 · a^1. You get a, a², a⁴, a⁸ by repeated squaring — one multiply each — and combine the ones whose bit is set.

Two small checks make the binary trick feel inevitable rather than clever. First, the digits: 1101 reads as 8 + 4 + 0 + 1, and 8 + 4 + 1 = 13. Second, the exponent law you've known since school: multiplying powers adds exponents, so a^8 · a^4 · a^1 = a^(8+4+1) = a^13. That is the whole justification, and nothing in it is special to 13. The loop squares once per bit and multiplies once per set bit, so 1101 costs 4 squarings and 3 multiplies — the same 7 operations measured below. One more fact keeps the modulus honest: (x · y) mod m = ((x mod m) · (y mod m)) mod m. Reducing early never changes the final remainder, which is why the running number stays small the whole way.

def modpow(a, b, m):
    result = 1
    a %= m
    while b > 0:
        if b & 1:                     # this bit of the exponent is set
            result = (result * a) % m # …so fold a's current power in
        a = (a * a) % m               # square: a → a² → a⁴ → a⁸ …
        b >>= 1                        # drop that bit
    return result

modpow(7, 13, 11)          # 2       — matches Python's built-in pow(7,13,11)
modpow(2, 1_000_000, 1_000_000_007)   # done in ~20 squarings, not a million

The loop runs once per bit of the exponent, so it does about log₂(b) squarings — O(log b). Measured: 7^13 mod 11 takes 4 squarings and 3 multiplies, 7 operations instead of 12. Every result matches Python's built-in pow(a, b, m), which is this algorithm under the hood. Now the showstopper: 2^1,000,000 mod (10⁹+7), where a naive approach wants 999,999 multiplications and this does 20 squarings and 7 multiplies. Twenty-seven operations to raise 2 to the millionth power. That single collapse, from a million down to twenty, is what makes public-key cryptography physically possible.

Fast modular power plus big primes is almost the whole recipe for the padlock in your address bar. Time to assemble it →

07RSA: why big primes keep your secrets

Here's the asymmetry everything rests on. Multiplying two large primes is trivial: p × q = n, instant. Going backwards means recovering p and q from n alone, and no known fast method exists. The best algorithms take astronomically long for numbers a few hundred digits wide. It's a one-way street, easy forward and effectively impossible back — that gap is a trapdoor, and RSA is built on it. First you need big primes, and here trial division dies. Checking a 19-digit number like 2⁶¹−1 took about 70 seconds on this machine. The probabilistic Miller-Rabin test answered in roughly a ten-thousandth of a second — a gap of order a half-million-fold here, though timings vary by machine. Miller-Rabin works by asking a few clever "if this were prime, this equation would hold" questions, each checked with fast modular power. It says "almost certainly prime," and you can drive the error probability below the chance of a cosmic ray flipping your answer. You'll meet the randomness behind it in chapter 46.

Before the line-by-line, let's build the demo's numbers ourselves, so nothing arrives by magic. Pick two small primes: p = 61 and q = 53. Multiply them and you get the public modulus: 61 × 53 = 3233. Next comes φ, which for a product of two primes is (p−1) × (q−1) = 60 × 52 = 3120. Now choose a public exponent, e = 17, and use Euclid's machinery to find the partner d with e · d mod φ = 1. Check the chapter's pair by hand: 17 × 2753 = 46,801, and 46,801 = 15 × 3120 + 1. The remainder is 1, exactly as required. That innocent 1 is the entire mechanism. Encrypt-then-decrypt raises the message to the power e·d, and a classical theorem says an exponent of 15·3120 + 1 acts on the message exactly like an exponent of 1. So the message comes back untouched. And since computing φ needs p and q, an attacker who can't factor n can never reach d.

p, q = 61, 53                 # (real RSA uses ~300-digit primes)
n   = p * q                   # 3233   — public
phi = (p-1) * (q-1)           # 3120   — secret, needs p and q
e   = 17                      # public exponent
d   = pow(e, -1, phi)         # 2753   — private key (modular inverse of e)

c = pow(65, e, n)             # encrypt message 65 → 2790   (public key)
m = pow(c, d, n)              # decrypt 2790      → 65     (private key)

Line by line: n = 3233 is public and e = 17 is public, and together they're the padlock anyone can snap shut. The private key d = 2753 is the modular inverse of e — the number that undoes it, mod φ. Computing φ = 3120 requires knowing p and q. Encrypting is one fast modular power: 65^17 mod 3233 = 2790. Decrypting is another: 2790^2753 mod 3233 = 65, the original, back exactly (verified). An attacker sees n, e, and the ciphertext 2790. But to get d they must factor n, and that's the wall. Every ingredient came from this chapter: big primes from Miller-Rabin, the encrypt and decrypt operations from fast modular power, and the key from the modular inverse via Euclid.

import math


def tile(w, h):
    """Cut a w x h floor into the biggest squares that leave no cut tile.
       Each leftover strip IS the same problem, smaller. Returns (side, cuts)."""
    cuts = []
    a, b = max(w, h), min(w, h)
    while b:
        q, r = divmod(a, b)                 # q squares of side b, remainder r
        cuts.append((q, b, r))
        a, b = b, r
    return a, cuts


side, cuts = tile(1071, 462)
print("floor 1071 x 462")
for q, s, r in cuts:
    print(f"   cut {q} square(s) of {s}x{s}  ->  strip {s} x {r} left")
print("tile that fits:", side, "| math.gcd:", math.gcd(1071, 462))
print("check:", 1071 % side, 462 % side, (1071 // side) * (462 // side), "tiles")


def egcd(a, b):
    """Extended Euclid: return (g, x, y) with a*x + b*y == g == gcd(a, b)."""
    old_r, r = a, b
    old_x, x = 1, 0
    old_y, y = 0, 1
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_x, x = x, old_x - q * x
        old_y, y = y, old_y - q * y
    return old_r, old_x, old_y


for a, b in [(1071, 462), (240, 46), (17, 3120)]:
    g, x, y = egcd(a, b)
    print(f"egcd({a}, {b}) = ({g}, {x}, {y})  check {a}*{x} + {b}*{y} ="
          f" {a*x + b*y}  gcd ok: {g == math.gcd(a, b)}")


def inverse(a, m):
    """a's partner mod m: the number that undoes it. Only exists if gcd(a,m)==1."""
    g, x, _ = egcd(a, m)
    if g != 1:
        raise ValueError(f"{a} has no inverse mod {m}: gcd is {g}")
    return x % m


print("inverse(17, 3120) =", inverse(17, 3120), "| pow(17, -1, 3120) =",
      pow(17, -1, 3120), "| 17*2753 mod 3120 =", 17 * 2753 % 3120)
try:
    inverse(6, 12)
except ValueError as err:
    print("ValueError:", err)

# the whole padlock, out of two functions you just wrote
p, q, e = 61, 53, 17
n, phi = p * q, (p - 1) * (q - 1)
d = inverse(e, phi)
msg = 65
c = pow(msg, e, n)
print(f"n={n} phi={phi} d={d} | encrypt({msg}) -> {c} | decrypt({c}) -> {pow(c, d, n)}")

worst = (832040, 514229)
print("Fibonacci worst case:", len(tile(*worst)[1]), "remainder steps, gcd =",
      tile(*worst)[0])


# ---------- the actual run, python 3.12.7 ----------
#
# floor 1071 x 462
#    cut 2 square(s) of 462x462  ->  strip 462 x 147 left
#    cut 3 square(s) of 147x147  ->  strip 147 x 21 left
#    cut 7 square(s) of 21x21  ->  strip 21 x 0 left
# tile that fits: 21 | math.gcd: 21
# check: 0 0 1122 tiles
# egcd(1071, 462) = (21, -3, 7)  check 1071*-3 + 462*7 = 21  gcd ok: True
# egcd(240, 46) = (2, -9, 47)  check 240*-9 + 46*47 = 2  gcd ok: True
# egcd(17, 3120) = (1, -367, 2)  check 17*-367 + 3120*2 = 1  gcd ok: True
# inverse(17, 3120) = 2753 | pow(17, -1, 3120) = 2753 | 17*2753 mod 3120 = 1
# ValueError: 6 has no inverse mod 12: gcd is 6
# n=3233 phi=3120 d=2753 | encrypt(65) -> 2790 | decrypt(2790) -> 65
# Fibonacci worst case: 28 remainder steps, gcd = 1
#
#
# ---------- reading it ----------
#
# 1. Three passes. Not three hundred. The naive way -- test 462, then 461,
#    then 460, down to 21 -- is 442 divisions; Euclid did it in 3, because
#    every pass replaces the bigger number with something strictly smaller
#    than the smaller one.
#
# 2. The room really does close: 1071 % 21 and 462 % 21 are both 0, and it
#    takes exactly 51 x 22 = 1122 tiles. The gcd is not an abstraction here.
#    It is the largest square that divides BOTH sides, which is the same
#    sentence as "the largest number dividing both".
#
# 3. egcd runs the identical remainder chain and just carries two extra
#    columns. That is the whole extension -- and those columns are what
#    turn "what is the gcd?" into "which combination of a and b MAKES the
#    gcd?", which is the question a private key is the answer to.
#
# 4. inverse(17, 3120) and pow(17, -1, 3120) both say 2753, and
#    17 * 2753 % 3120 == 1. So d is not a magic number handed down by RSA:
#    it is the second column of a 2,000-year-old division loop.
#
# 5. inverse(6, 12) refuses, and refusing is correct. On a 12-dial, every
#    multiple of 6 lands on 0 or 6 -- 1 is unreachable, so no inverse
#    exists. gcd(a, m) == 1 is not a formality; it is the existence proof.
#
# 6. Fibonacci: 28 passes for numbers around 800,000. Every quotient is 1,
#    so each pass peels off the smallest possible amount -- the slowest
#    Euclid can ever be. And 28 is still nothing. That is the point: even
#    the worst case of this algorithm is logarithmic.

Miller-Rabin only worked by flipping a coin — it trusts randomness to be almost-certainly right, fast. That's not a hack; it's a whole design philosophy. Chapter 46 makes randomness your armor: a random pivot that defeats any adversary, and estimating answers you can't compute by throwing darts →