45Strings & number theory — the crypto and quant layer

In Chapter 44 we turned almost every hard problem into dots and lines, and walked the graph three ways. Here we pick up two toolkits that punch far above their weight. 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: primes, remainders, and one calculation that is easy to run forward and effectively impossible to run backward. Both halves keep asking the same question, and it's the one that 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 work out why the naive scan is slow and how to fix it, sieve every prime up to a million by pure elimination, raise a number to the millionth power in about twenty multiplications, and 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. It always finds the match. 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 the two and the worst case is (n − m + 1) · m comparisons — that's 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; line 6 compares until a mismatch. The pathological string "a"×20 + "b" against "aaaab" costs 85 comparisons (verified). At each of 17 positions it matches four as, then 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.

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. You can feel it before you see any machinery. When the pattern aaaab matches four as and 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. That means there is no reason to ever walk the text pointer backwards. None.

KMP precomputes, from the pattern alone, a small table. It 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. Each text character is looked at essentially once, so the whole search is O(n + m) — the n to scan the text plus the m to build the table. That's 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; the naive scan read 85. On the big string it is 10,001 versus 990,200, a gap that 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.

03Rabin-Karp: slide a hash over the text

Different idea, same enemy: re-work. Instead of comparing 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 two numbers differ, the chunks differ, so you skip the comparison entirely. The catch is that computing a fresh hash for every window would itself be O(m) per window, O(n·m) total — no win. The move that saves it is a rolling hash. When the window slides one step, don't recompute — update. Subtract the character leaving the left, shift, then add the character entering 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, one digit per byte. Sliding right is exactly like turning 734 into 345: drop the leading digit's place value, multiply by the base, then add the new trailing digit. It's all done modulo a big prime so the number stays small.

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 -

Run it on "the cat sat on the mat" searching "cat": the pattern hashes to 6513012, and the window slides 19 times. Here's the honesty check: every single rolling update was compared against a hash computed from scratch, and matched exactly. The match is reported at index 4, the same spot the naive scan found. Where a hash collides — two different chunks with the same fingerprint — 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 you wrap around after 12. Write it 15 mod 12 = 3. 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.

The greatest common divisor (GCD) of two numbers is the largest number that divides both. The naive way is to test every candidate down from the smaller number, which is O(min(a,b)). Euclid's insight, over two thousand years old and still unbeaten, fits in 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.

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: 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.

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. Primes are 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 the 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, and cross out every multiple of 3. Do the same for the next survivor, 5. Whatever is never crossed out is prime, because a composite number is by definition a multiple of some smaller prime.

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: any composite ≤ n has a factor no larger than its square root, so once you've sieved with primes up to √n, everything left is prime. Line 7 starts crossing at p², not 2p, because the smaller multiples of p (like 2p, 3p) were already crossed by smaller primes. The cost is startling: O(n log log n), which grows so slowly that log log n is 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, so a^13 = a^8 · a^4 · a^1. You build a, a², a⁴, a⁸ by repeated squaring, one multiply each, and combine the ones whose bit is set.

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, and every result matches Python's built-in pow(a, b, m), which is this algorithm. Now the showstopper: 2^1,000,000 mod (10⁹+7). A naive approach wants 999,999 multiplications; this does 20 squarings and 7 multiplies. That's twenty-seven operations to raise 2 to the millionth power. That single collapse from a million 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 — given only n, recover p and q — has no known fast method. The best algorithms take astronomically long for numbers a few hundred digits wide. It's a one-way street: easy forward, 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 — it asks a few clever "if this were prime, this equation would hold" questions using fast modular power. (That's a gap of order half a million-fold here; timings vary by machine.) Miller-Rabin 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.

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 and e = 17 are both public. 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 φ), and 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 is from this chapter: big primes (Miller-Rabin), the encrypt/decrypt operations (fast modular power), and the key (modular inverse via Euclid).

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 →