Capstone: A Tiny Crypto & Numerics Toolkit
Module 8 was a tour of the mathematics that hides inside everyday software: the primes behind every HTTPS padlock, the fast transforms behind big-number libraries and signal processing, the cross products behind every map, and the game values behind every "who wins?" puzzle. In this capstone you put those pieces together into one small toolkit, numkit, and you test every piece against something independent: Python's built-in arithmetic, a sieve, a brute-force oracle, or an exhaustive game-tree search.
You will build four things:
- Toy RSA from scratch: Miller–Rabin primes, the extended Euclidean algorithm for the private key, and square-and-multiply for encryption and decryption.
- Big-integer multiplication with the NTT (the number-theoretic transform), benchmarked against the schoolbook method you learned at age eight.
- The convex hull and area of a generated "city" of 20,000 GPS pings, checked against an oracle.
- Sprague–Grundy values verified by brute force: compute Grundy numbers for two games, then confirm by exhaustive search that the XOR rule predicts the winner of every sum of three games you try.
This is Module 8 applied. It uses Number Theory I (Euclid, extended Euclid, sieves), Modular Arithmetic (fast powers, inverses, the Chinese Remainder Theorem, the 998244353 modulus), Number Theory II (Miller–Rabin), FFT & NTT, Computational Geometry and Game Theory. Combinatorics, Probability & Expected Value and Linear Algebra show up in the extension ideas.
This RSA is a toy. Do not use it to protect anything.
Textbook RSA (no padding) is deterministic (the same message always encrypts to the same ciphertext, so an attacker can test guesses), malleable (multiplying two ciphertexts gives the encryption of the product of the messages; the acceptance tests demonstrate it), and broken outright for small messages with small exponents. The reference code also uses Python's random module, which is not a cryptographic random number generator, and big-integer arithmetic whose running time depends on the secret key (a timing side channel). Real systems use a vetted library (OpenSSL, BoringSSL, libsodium, Go's crypto, Python's cryptography), keys of at least 2,048 bits, OAEP padding for encryption and PSS for signatures (RFC 8017), or, more often today, elliptic-curve schemes. Writing RSA yourself is how you learn it, never how you ship it. See Symmetric vs Asymmetric Encryption and Cryptography for Engineers.
Goal
Build a single Python module, numkit, with four parts and one benchmark:
generate_keys(bits),encrypt_text,decrypt_text: RSA key generation from Miller–Rabin primes, encryption and decryption of short UTF-8 messages, and CRT-accelerated decryption.multiply_ntt(x, y): exact product of two non-negative decimal strings by one NTT convolution modulo 998244353, plusmultiply_schoolbookas the baseline.convex_hull(points),twice_area(polygon): Andrew's monotone chain and the shoelace formula, run on a reproducible synthetic data set.grundy_subtraction,grundy_split,brute_wins_*: Grundy numbers by the mex rule, and a game-tree search that knows nothing about Grundy numbers, to check them against.benchmark(): schoolbook versus NTT versus Python's built-inint, from 100 to 32,000 digits; key generation time; decryption with and without the CRT.
Every function is checked against an independent oracle. The reference solution is a single tested file using only the standard library; port it to your working language if you like (C++ and Rust make the NTT about 50–100× faster).
Requirements
- Modular exponentiation. Iterative square-and-multiply, multiplications. Must agree with Python's three-argument
powon random inputs (andpower_mod(x, 0, 1)must be 0, since everything is 0 modulo 1). - Extended Euclid. Iterative (no recursion limit for 2,048-bit inputs). Returns with .
mod_inverseraises on non-invertible inputs. - Miller–Rabin. Trial division by small primes first, then random bases. Must agree with a sieve on every , reject Carmichael numbers, and accept Mersenne primes and .
- Keys. has exactly the requested number of bits, , , where is Carmichael's function. Messages are encoded as one big-endian integer smaller than ; longer messages are rejected (no chunking in a toy).
- NTT multiplication. Digits base 10, least significant first; the transform length is the next power of two at or above ; final carry pass; no leading zeros;
"0"handled. State and assert the size limit under which a single prime gives exact results. - Hull. Strictly convex, counter-clockwise, duplicates removed; area via the shoelace formula in integers ("twice the area").
- Games. Grundy numbers by mex; the brute-force solver works on whole positions (tuples of heaps) and never uses XOR.
- Tests. The acceptance tests below pass in under 5 seconds; the benchmark runs separately.
Getting the data
Everything runs offline and is reproducible from fixed seeds.
- RSA. Keys from
random.Random(42); messages include non-ASCII text ("Grüße, 世界") to make sure you encode bytes, not characters. - Big integers. Random digit strings from
random.Random(7). Python's ownintis the oracle. Python 3.11 and later refuse to convert integers of more than 4,300 digits to and from strings by default (a guard against denial-of-service on parsers); the reference lifts the limit withsys.set_int_max_str_digits(0). That was the first failure hit while writing this page. - The city. A real data set would be a day of anonymised GPS pings from a delivery fleet. The reference generates a stand-in: a convex 12-sided "city boundary" in metres (about 10.6 km × 9.6 km), five Gaussian "neighbourhood" clusters with a standard deviation of 900 m holding 70% of the pings, and 30% spread uniformly, all rejected unless inside the boundary. 20,000 integer points, seed 2026.
- Games. Two impartial games: the subtraction game with moves (take 1, 3 or 4 tokens from a heap), and Grundy's game (split one heap into two non-empty heaps of different sizes). Whoever cannot move loses (normal play).
flowchart LR
MR["Miller-Rabin primes p, q"] --> KEY["n = p*q, lambda = lcm(p-1, q-1)"]
KEY --> EUC["d = inverse of e mod lambda (extended Euclid)"]
EUC --> ENC["c = m^e mod n (square-and-multiply)"]
ENC --> DEC["m = c^d mod n, or CRT: two half-size powers"]
DIG["Digit lists"] --> NTT["NTT both, multiply pointwise, inverse NTT"]
NTT --> CAR["Carry pass"]
PTS["20,000 pings"] --> HULL["Monotone chain hull"]
HULL --> AREA["Shoelace area"]
MEX["Grundy by mex"] --> CHK["Compare XOR rule with brute-force game search"]
The staged plan
Part 1 — Toy RSA: keys, encryption, decryption
The idea. Pick two large primes and and publish together with an exponent . Anyone can encrypt a number as . Only someone who knows a with can undo it: . Computing requires , which requires the factors, and factoring a 2,048-bit is far beyond any known classical algorithm. (Rivest, Shamir and Adleman, CACM 21(2), 1978; the original paper uses , which also works because divides .) Modular Arithmetic proves why decryption works.
Step 1: primes. Draw random odd numbers of the right bit length (set the top bit so the size is exact, and the bottom bit so it is odd) and test each with Miller–Rabin until one passes. By the prime number theorem, about 1 in numbers near is prime, so about 1 in 177 odd ones: a few hundred tests per prime. Trial division by the primes below 200 rejects about 90% of candidates before any expensive exponentiation (the fraction of numbers with no prime factor below 200 is ).
Miller–Rabin in one paragraph (full treatment in Number Theory II). Write with odd. For a random base , compute and square it up to times. If is prime, the sequence either starts at 1 or hits , because the only square roots of 1 modulo a prime are . If it does neither, is a witness and is certainly composite. For any odd composite , at most a quarter of bases fail to be witnesses (Rabin, 1980), so 40 independent rounds leave an error probability below , and for random candidates the true error is far smaller still (Damgård, Landrock and Pomerance, 1993). Carmichael numbers such as 561, which fool the plain Fermat test for every base coprime to them, do not fool Miller–Rabin.
Step 2: the private exponent. With (: prime, and only two 1-bits, so encryption is 17 multiplications), check (otherwise pick new primes) and compute with the extended Euclidean algorithm (Number Theory I).
A worked example small enough to check by hand (the classic one from Wikipedia's RSA article): , , , , . Extended Euclid on , tracking only the coefficient of 17:
| Step | |||||
|---|---|---|---|---|---|
| 1 | 3120 | 17 | 183 | 0 | 1 |
| 2 | 17 | 9 | 1 | 1 | −183 |
| 3 | 9 | 8 | 1 | −183 | 184 |
| 4 | 8 | 1 | 8 | 184 | −367 |
| end | 1 | 0 | — | −367 |
So , and . (Using instead gives the smaller ; both decrypt correctly.)
Encrypt : by square-and-multiply, reading the exponent from the low bit:
| Remaining | Low bit | Result | |
|---|---|---|---|
| 17 | 1 | 65 | 65 |
| 8 | 0 | 992 | 65 |
| 4 | 0 | 1232 | 65 |
| 2 | 0 | 1547 | 65 |
| 1 | 1 | 789 | 2790 |
Five squarings instead of sixteen multiplications. Decryption: , and also .
Step 3: messages. Encode the UTF-8 bytes of the text as one big-endian integer , require , encrypt, decrypt, decode. A 512-bit key holds about 63 bytes.
Step 4: faster decryption with the CRT. The private-key holder knows and , so compute and and combine them with the Chinese Remainder Theorem (Garner's formula: ). Each exponentiation has half-size numbers and a half-size exponent, so in theory it is about 4× cheaper per power and 2 powers: about 2× to 4× overall. Every real RSA implementation does this (the "CRT form" of the private key in PKCS #1 stores exactly , and ). Benchmark it.
Famous real failures of "correct" RSA
- Bad randomness. In 2008, a patch to Debian's OpenSSL package (CVE-2008-0166) left the random generator seeded with little more than the process ID, so only about 32,768 possible keys per key type and size could be generated, and every one of them could be precomputed. In 2012, Heninger et al. ("Mining Your Ps and Qs", USENIX Security) and Lenstra et al. ("Ron was wrong, Whit is right") found that a fraction of a percent of the RSA keys on the internet shared a prime with another key, and factored them all with a batch GCD.
- Structured primes. The ROCA flaw (Nemec et al., CCS 2017) showed that an Infineon library generated primes of a special form that made the keys factorable; it affected Estonia's national ID cards among other things.
- Padding oracles. Bleichenbacher (CRYPTO 1998) decrypted PKCS #1 v1.5 messages by sending about a million crafted ciphertexts to a server and watching which ones it rejected.
Part 2 — Big-integer multiplication with the NTT
The idea. Multiplying two numbers is a convolution of their digit sequences followed by carrying. With and , the product is with . Schoolbook computes every : . The fast Fourier transform computes a convolution in , where is the result length rounded up to a power of two: transform both sequences, multiply pointwise, transform back. The NTT is the same algorithm over integers modulo a prime that has -th roots of unity, so every step is exact (no rounding).
Why 998244353? It equals , so its multiplicative group (order ) contains roots of unity of every power-of-two order up to , and 3 is a primitive root. A root of order is . See Modular Arithmetic and FFT & NTT.
The exactness condition. The NTT computes , not . It is exact only if every true . With base-10 digits, , so a single prime is exact while the shorter number has fewer than million digits; the transform length is the tighter limit (about 4.2 million digits each). The reference asserts the bound. Bigger digit bases (say per limb) make the transform 4× shorter but up to , which overflows one prime at once: then you use three NTT primes and recombine each coefficient with the CRT, or a floating-point FFT with careful error bounds. That trade-off is extension idea 2.
Steps.
- Digits least significant first:
"1234"→[4, 3, 2, 1]. - Pad both to length , the smallest power of two .
- Forward NTT of both (iterative Cooley–Tukey: bit-reversal permutation, then levels of butterflies , ).
- Pointwise product modulo .
- Inverse NTT (the same with , then multiply by ).
- Carry: walk the coefficients, keep
carry % 10, passcarry // 10on.
Small check: .
What to benchmark. For digits: schoolbook, NTT, and Python's built-in int multiplication, best of 3. Predict the shape before you run it: schoolbook ×4 per doubling, NTT a bit over ×2, and the built-in somewhere in between (CPython multiplies large integers with Karatsuba, ; see Divide & Conquer).
Part 3 — Convex hull and area of a city of GPS pings
The question. Given every location a delivery fleet reported in a day, what is the smallest convex region that covers them, and how big is it? (That is a crude service-area estimate. Real systems use concave hulls or polygons of H3/S2 cells, but the convex hull is the first thing to compute and the yardstick for the rest.)
Steps.
- Generate the 20,000 pings (see Getting the data). Coordinates are integer metres in a local planar frame, so every predicate is exact. (With real latitude/longitude you would first project to a local metric frame such as UTM; see Geospatial Engineering.)
- Compute the hull with Andrew's monotone chain (Computational Geometry): sort, then a lower and an upper chain with "pop while not a left turn".
- Area with the shoelace formula in integers; the sign doubles as a check that the hull is counter-clockwise.
- Verify: every ping is inside or on the hull (one orientation test per edge per ping, 20,000 × 49); every hull turn is strictly left; the hull of the first 400 pings equals an brute-force oracle (a pair is a hull edge iff no point is to its right or beyond its ends on the same line); 300 random small point sets with many collinear points and duplicates agree with the oracle too.
- Sanity: the hull must lie inside the city boundary (the pings do), so its area is less than the city's; with this many pings it should be close.
Expected numbers. The city boundary has twice-area 161,430,000 m² (80.72 km²). The hull of the 20,000 pings has 49 vertices and twice-area 160,104,660 (80.05 km², 99.2% of the city). A hull with 49 corners for 20,000 points is typical: for points uniform in a convex polygon with corners, the expected number of hull vertices grows only like plus a constant (Rényi and Sulanke, 1963), which is about 79 for and ; our points are less uniform (70% are in clusters), so fewer of them reach the boundary.
Optional: the farthest pair of pings with rotating calipers, checked against brute force over the hull's pairs.
Part 4 — Sprague–Grundy, verified by brute force
The theory (Game Theory; also Game DP). In an impartial game under normal play, every position has a Grundy number: the mex (minimum excluded non-negative integer) of the Grundy numbers of the positions reachable in one move. A position is a loss for the player to move iff its Grundy number is 0. The Sprague–Grundy theorem (Sprague 1935, Grundy 1939) says that a sum of games (a move is a move in exactly one component) has Grundy number equal to the XOR of the components' Grundy numbers. So "who wins three heaps?" reduces to three table lookups and two XORs.
That theorem is the kind of statement that is easy to misapply (to games that are not impartial, to misère play, or to moves that touch two components). So test it on your own games.
Steps.
- Subtraction game . Compute by mex. You should get repeating with period 7. (Every subtraction game with a finite move set is eventually periodic, because depends only on the previous values, which can take finitely many combinations.)
- Brute force without Grundy numbers. Write
win(state)on whole positions (sorted tuples of heap sizes): a position is a win iff some move leads to a losing position. Memoise it. It knows nothing about XOR. - Compare. For every with (2,197 positions),
win((a, b, c))must equal . - Grundy's game. Splitting a heap of into with creates two heaps, so : the XOR rule is already used inside the recurrence. Compute ; it starts 0, 0, 0, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 3, 2, 1, 3, 2, 4, 3, 0 (OEIS A002188). Then brute-force every three-heap position with heaps and total at most 24 (336 positions) by searching over multisets of heaps, and compare.
Nobody knows whether Grundy's game is eventually periodic; it has been computed to enormous heap sizes without a period appearing (Berlekamp, Conway and Guy, Winning Ways, discuss it). Your brute force cannot settle that, but it does confirm that the XOR rule holds for every position you can afford to search, which is the point: trust theorems, verify implementations.
Milestones
| # | Milestone | Done when |
|---|---|---|
| 1 | power_mod, ext_gcd, mod_inverse | agree with pow(b, e, m) and pow(a, -1, m) on 500 random inputs; the 3233 example reproduces , |
| 2 | Miller–Rabin | equals a sieve on ; rejects 10 Carmichael numbers; accepts and ; rejects |
| 3 | RSA keys and messages | 512-bit exactly; three messages round-trip, including non-ASCII; 50 random integers round-trip with and without the CRT |
| 4 | NTT | equals Python int on 200 random pairs of up to 300 digits and on two 20,000-digit numbers; schoolbook agrees on the small ones |
| 5 | Benchmark | a table of time for 8 sizes, with an explanation of each column's growth |
| 6 | Hull and area | oracle agreement on 300 small sets and on 400 pings; 49 vertices, twice-area 160,104,660 on the full set |
| 7 | Grundy | period 7 for ; 2,197 + 336 brute-force positions agree with XOR |
| 8 | CLI | numkit rsa-demo, numkit mul X Y, numkit hull FILE, numkit grundy wired up (left to you: a few lines of argparse) |
Acceptance tests
Your toolkit passes when:
| Test | Expected |
|---|---|
power_mod(4, 13, 497), power_mod(5, 0, 1) | 445, 0 |
ext_gcd(240, 46); mod_inverse(17, 3120) | (2, -9, 47); 2753 |
| Miller–Rabin vs sieve, | identical |
| Carmichael 561, 1105, 1729, 2465, 2821, 6601, 8911, 41041, 825265, 321197185 | all composite |
| , / | prime / composite |
| ; | 2790; 65 |
generate_keys(512, rng=Random(42)) | has 512 bits, , |
Encrypt/decrypt "hello", "RSA is a toy here", "Grüße, 世界" | round-trip; ciphertext differs from plaintext |
| 50 random | decrypt_int == decrypt_crt == m |
| Malleability | |
multiply_ntt("12345678", "87654321") | "1082152022374638" |
multiply_ntt("0", "999"), ("1", "1"), | "0", "1", matches Python |
| 200 random pairs up to 300 digits; one 20,000-digit pair | NTT = schoolbook = Python |
| Hull vs oracle on 300 random sets of ≤ 15 points on a 9×9 grid | identical vertex sets |
| City: 20,000 pings | all inside the hull; hull strictly convex; 49 vertices; twice-area 160,104,660; city twice-area 161,430,000 |
| Grundy | first 14: 0 1 0 1 2 3 2 0 1 0 1 2 3 2; period 7 up to 60 |
| Grundy's game | first 14: 0 0 0 1 0 2 1 0 2 1 0 2 1 3 |
| XOR rule vs brute force | 2,197 subtraction-game and 336 Grundy's-game positions agree |
Reference solution
Reference solution (Python, tested)
One file, standard library only (Python 3.9+ for math.lcm). python3 numkit.py runs every acceptance test in about 2 seconds; python3 numkit.py --bench runs the benchmarks (about 15 seconds). The CLI wrapper (milestone 8) is left to you.
"""Module 8 capstone reference solution: toy RSA, NTT big-integer multiplication,
convex hull + area of a generated point set, Sprague-Grundy verified by brute force.
Run `python3 numkit.py` for the acceptance tests, `python3 numkit.py --bench` for the benchmarks.
TOY CODE: the RSA here is textbook RSA without padding. Never use it to protect anything.
"""
import math
import random
import sys
import time
from functools import lru_cache
if hasattr(sys, "set_int_max_str_digits"): # Python 3.11+ caps int<->str at 4,300 digits by default
sys.set_int_max_str_digits(0)
# ------------------------------------------------------------ Part 1: toy RSA
def power_mod(base, exp, mod):
"""Square-and-multiply: base**exp % mod in O(log exp) multiplications."""
result, base = 1 % mod, base % mod
while exp > 0:
if exp & 1:
result = result * base % mod
base = base * base % mod
exp >>= 1
return result
def ext_gcd(a, b):
"""Return (g, x, y) with a*x + b*y = g = gcd(a, b). Iterative, so no recursion limit."""
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
def mod_inverse(a, m):
g, x, _ = ext_gcd(a % m, m)
if g != 1:
raise ValueError(f"{a} has no inverse modulo {m}")
return x % m
SMALL_PRIMES = [p for p in range(2, 200) if all(p % q for q in range(2, int(p ** 0.5) + 1))]
def is_probable_prime(n, rounds=40, rng=random):
"""Miller-Rabin. Composite numbers pass one random round with probability at most 1/4."""
if n < 2:
return False
for p in SMALL_PRIMES: # trial division: fast rejection, and small n
if n % p == 0:
return n == p
d, s = n - 1, 0
while d % 2 == 0: # n - 1 = d * 2^s with d odd
d //= 2
s += 1
for _ in range(rounds):
a = rng.randrange(2, n - 1)
x = power_mod(a, d, n)
if x in (1, n - 1):
continue
for _ in range(s - 1):
x = x * x % n
if x == n - 1:
break
else:
return False # a is a witness: n is certainly composite
return True
def random_prime(bits, rng):
while True:
n = rng.getrandbits(bits) | (1 << (bits - 1)) | 1 # exactly `bits` bits, odd
if is_probable_prime(n, rng=rng):
return n
def generate_keys(bits=512, e=65537, rng=None):
"""Return ((n, e), (n, d)). bits is the size of n. Toy: no safeguards beyond the basics."""
rng = rng or random.Random()
while True:
p = random_prime(bits // 2, rng)
q = random_prime(bits - bits // 2, rng)
if p == q:
continue
lam = math.lcm(p - 1, q - 1) # Carmichael's function of n = p*q
if math.gcd(e, lam) != 1:
continue
n = p * q
if n.bit_length() != bits:
continue
d = mod_inverse(e, lam)
return (n, e), (n, d), (p, q)
def encrypt_int(m, public):
n, e = public
if not 0 <= m < n:
raise ValueError("message must be an integer in [0, n)")
return power_mod(m, e, n)
def decrypt_int(c, private):
n, d = private
return power_mod(c, d, n)
def decrypt_crt(c, p, q, d):
"""Same result as decrypt_int, faster: two half-size exponentiations, recombined by the CRT."""
dp, dq, q_inv = d % (p - 1), d % (q - 1), mod_inverse(q, p)
m1, m2 = power_mod(c, dp, p), power_mod(c, dq, q)
h = q_inv * (m1 - m2) % p
return m2 + h * q
def encrypt_text(text, public):
data = text.encode("utf-8")
n = public[0]
if len(data) >= (n.bit_length() - 1) // 8:
raise ValueError("message too long for this key (toy RSA encrypts one block)")
return encrypt_int(int.from_bytes(data, "big"), public)
def decrypt_text(c, private):
m = decrypt_int(c, private)
return m.to_bytes((m.bit_length() + 7) // 8, "big").decode("utf-8")
# ---------------------------------------------- Part 2: NTT big-integer multiplication
MOD = 998244353 # 119 * 2^23 + 1, so it has 2^23-th roots of unity
ROOT = 3 # a primitive root modulo MOD
def ntt(a, invert=False):
"""In-place iterative Cooley-Tukey NTT. len(a) must be a power of two <= 2^23."""
n = len(a)
j = 0
for i in range(1, n): # bit-reversal permutation
bit = n >> 1
while j & bit:
j ^= bit
bit >>= 1
j |= bit
if i < j:
a[i], a[j] = a[j], a[i]
length = 2
while length <= n:
w_len = pow(ROOT, (MOD - 1) // length, MOD)
if invert:
w_len = pow(w_len, MOD - 2, MOD)
half = length // 2
ws = [1] * half # powers of w_len, computed once per level
for k in range(1, half):
ws[k] = ws[k - 1] * w_len % MOD
for start in range(0, n, length):
for k in range(half):
u = a[start + k]
v = a[start + k + half] * ws[k] % MOD
a[start + k] = (u + v) % MOD
a[start + k + half] = (u - v) % MOD
length <<= 1
if invert:
n_inv = pow(n, MOD - 2, MOD)
for i in range(n):
a[i] = a[i] * n_inv % MOD
def digits_of(s):
"""Decimal string -> list of digits, least significant first."""
return [int(ch) for ch in reversed(s)]
def carry_to_string(coeffs):
out, carry = [], 0
for c in coeffs:
carry += c
out.append(carry % 10)
carry //= 10
while carry:
out.append(carry % 10)
carry //= 10
while len(out) > 1 and out[-1] == 0:
out.pop()
return "".join(map(str, reversed(out)))
def multiply_ntt(x, y):
"""Multiply two non-negative decimal strings with one NTT convolution of their digits."""
a, b = digits_of(x), digits_of(y)
need = len(a) + len(b) - 1
# each convolution coefficient is at most min(len) * 81; it must stay below MOD to be exact
assert min(len(a), len(b)) * 81 < MOD, "inputs too long for a single-prime NTT"
n = 1
while n < need:
n <<= 1
a += [0] * (n - len(a))
b += [0] * (n - len(b))
ntt(a)
ntt(b)
c = [u * v % MOD for u, v in zip(a, b)]
ntt(c, invert=True)
return carry_to_string(c[:need])
def multiply_schoolbook(x, y):
"""Grade-school O(n*m) multiplication on digit lists."""
a, b = digits_of(x), digits_of(y)
c = [0] * (len(a) + len(b))
for i, da in enumerate(a):
if da == 0:
continue
for j, db in enumerate(b):
c[i + j] += da * db
return carry_to_string(c)
# ---------------------------------------------- Part 3: convex hull and area
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
def convex_hull(points):
"""Andrew's monotone chain. Strictly convex, counter-clockwise."""
pts = sorted(set(points))
if len(pts) <= 2:
return pts
lower, upper = [], []
for p in pts:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
for p in reversed(pts):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
return lower[:-1] + upper[:-1]
def twice_area(poly):
n = len(poly)
return sum(poly[i][0] * poly[(i + 1) % n][1] - poly[(i + 1) % n][0] * poly[i][1] for i in range(n))
def hull_brute(points):
"""O(n^3) oracle: directed edges (p, q) with every other point strictly left or on segment pq."""
pts = sorted(set(points))
if len(pts) <= 2:
return set(pts)
verts = set()
for p in pts:
for q in pts:
if p == q:
continue
ok = True
for r in pts:
c = cross(p, q, r)
if c < 0 or (c == 0 and (r[0] - p[0]) * (r[0] - q[0]) + (r[1] - p[1]) * (r[1] - q[1]) > 0):
ok = False # r right of pq, or collinear but outside segment pq
break
if ok:
verts.update((p, q))
return verts
# 12 corners of a "city boundary" (metres, counter-clockwise, convex) used to generate pings
CITY = [(0, 3000), (1500, 600), (4200, 0), (7600, 300), (9800, 1900), (10600, 4300),
(10000, 7000), (8200, 8800), (5400, 9600), (2600, 9100), (700, 7400), (0, 5200)]
def inside_convex(p, poly):
return all(cross(poly[i], poly[(i + 1) % len(poly)], p) >= 0 for i in range(len(poly)))
def generate_pings(n, seed=2026):
"""n integer points: 70% in 5 Gaussian 'neighbourhood' clusters, 30% uniform, all inside CITY."""
rng = random.Random(seed)
xs = [x for x, _ in CITY]
ys = [y for _, y in CITY]
centres = [(rng.randint(2500, 8000), rng.randint(2500, 7500)) for _ in range(5)]
pts = []
while len(pts) < n:
if rng.random() < 0.7:
cx, cy = rng.choice(centres)
p = (round(rng.gauss(cx, 900)), round(rng.gauss(cy, 900)))
else:
p = (rng.randint(min(xs), max(xs)), rng.randint(min(ys), max(ys)))
if inside_convex(p, CITY):
pts.append(p)
return pts
# ---------------------------------------------- Part 4: Sprague-Grundy by brute force
def mex(values):
m = 0
s = set(values)
while m in s:
m += 1
return m
def grundy_subtraction(limit, moves):
g = [0] * (limit + 1)
for n in range(1, limit + 1):
g[n] = mex(g[n - m] for m in moves if m <= n)
return g
def grundy_split(limit):
"""Grundy's game: split one heap into two non-empty heaps of different sizes."""
g = [0] * (limit + 1)
for n in range(3, limit + 1):
g[n] = mex(g[a] ^ g[n - a] for a in range(1, (n + 1) // 2) if a != n - a)
return g
def brute_wins_subtraction(heaps, moves):
"""Plain game-tree search on the whole position (a sorted tuple of heaps). No Grundy theory."""
@lru_cache(maxsize=None)
def win(state):
for i, h in enumerate(state):
for m in moves:
if m <= h:
nxt = tuple(sorted(state[:i] + (h - m,) + state[i + 1:]))
if not win(nxt):
return True
return False # no move, or every move lets the opponent win
return win(tuple(sorted(heaps)))
def brute_wins_split(heaps):
@lru_cache(maxsize=None)
def win(state):
for i, h in enumerate(state):
for a in range(1, (h + 1) // 2):
if a != h - a:
rest = state[:i] + state[i + 1:]
nxt = tuple(sorted(rest + (a, h - a)))
if not win(nxt):
return True
return False
return win(tuple(sorted(heaps)))
# ---------------------------------------------- acceptance tests
def run_tests():
rng = random.Random(1)
# Part 1 -----------------------------------------------------------------
assert power_mod(4, 13, 497) == 445 and power_mod(5, 0, 1) == 0
assert all(power_mod(b, e, m) == pow(b, e, m)
for b, e, m in ((rng.randrange(10**9), rng.randrange(10**9), rng.randrange(1, 10**9)) for _ in range(500)))
assert ext_gcd(240, 46) == (2, -9, 47) # 240*(-9) + 46*47 = 2
assert mod_inverse(17, 3120) == 2753 # the classic textbook RSA example
sieve = bytearray([1]) * 100_001
sieve[0] = sieve[1] = 0
for i in range(2, 317):
if sieve[i]:
sieve[i * i::i] = bytearray(len(sieve[i * i::i]))
assert all(is_probable_prime(k, rng=rng) == bool(sieve[k]) for k in range(100_001))
carmichael = [561, 1105, 1729, 2465, 2821, 6601, 8911, 41041, 825265, 321197185]
assert not any(is_probable_prime(c, rng=rng) for c in carmichael)
assert is_probable_prime(2**61 - 1, rng=rng) and is_probable_prime(2**127 - 1, rng=rng)
assert not is_probable_prime((2**61 - 1) * (2**31 - 1), rng=rng)
# the textbook example: p = 61, q = 53, n = 3233, e = 17, d = 2753 (with phi = 3120)
assert power_mod(65, 17, 3233) == 2790 and power_mod(2790, 2753, 3233) == 65
public, private, (p, q) = generate_keys(512, rng=random.Random(42))
n, e = public
assert n.bit_length() == 512 and p * q == n and e * private[1] % math.lcm(p - 1, q - 1) == 1
for msg in ["hello", "RSA is a toy here", "Grüße, 世界"]:
c = encrypt_text(msg, public)
assert c != int.from_bytes(msg.encode(), "big") and decrypt_text(c, private) == msg
for _ in range(50):
m = rng.randrange(n)
c = encrypt_int(m, public)
assert decrypt_int(c, private) == m == decrypt_crt(c, p, q, private[1])
# textbook RSA is deterministic and malleable: E(a) * E(b) = E(a * b mod n)
a, b = 1234, 5678
assert encrypt_int(a, public) * encrypt_int(b, public) % n == encrypt_int(a * b % n, public)
assert encrypt_int(a, public) == encrypt_int(a, public)
# Part 2 -----------------------------------------------------------------
assert multiply_ntt("12345678", "87654321") == str(12345678 * 87654321) == "1082152022374638"
assert multiply_ntt("0", "999") == "0" and multiply_ntt("1", "1") == "1"
assert multiply_ntt("9" * 1000, "9" * 1000) == str(int("9" * 1000) ** 2)
for _ in range(200):
x = str(rng.randrange(10 ** rng.randint(1, 300)))
y = str(rng.randrange(10 ** rng.randint(1, 300)))
expect = str(int(x) * int(y))
assert multiply_ntt(x, y) == expect == multiply_schoolbook(x, y)
big_x = "".join(rng.choice("0123456789") for _ in range(20_000)).lstrip("0") or "0"
big_y = "".join(rng.choice("0123456789") for _ in range(20_000)).lstrip("0") or "0"
assert multiply_ntt(big_x, big_y) == str(int(big_x) * int(big_y))
# Part 3 -----------------------------------------------------------------
for _ in range(300): # hull vs O(n^3) oracle on small sets
pts = [(rng.randint(0, 8), rng.randint(0, 8)) for _ in range(rng.randint(1, 15))]
hull = convex_hull(pts)
assert set(hull) == hull_brute(pts)
if len(hull) >= 3:
assert twice_area(hull) > 0
assert all(inside_convex(p, hull) for p in pts)
pings = generate_pings(20_000)
hull = convex_hull(pings)
area_hull = twice_area(hull) / 2
area_city = twice_area(CITY) / 2
assert len(pings) == 20_000 and all(inside_convex(p, hull) for p in pings)
assert all(cross(hull[i], hull[(i + 1) % len(hull)], hull[(i + 2) % len(hull)]) > 0 for i in range(len(hull)))
assert twice_area(CITY) == 161_430_000 and 0.97 * area_city < area_hull < area_city
assert (len(hull), twice_area(hull)) == (49, 160_104_660)
assert set(convex_hull(pings[:400])) == hull_brute(pings[:400])
# Part 4 -----------------------------------------------------------------
moves = (1, 3, 4)
g = grundy_subtraction(60, moves)
assert g[:14] == [0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2]
assert all(g[i] == g[i % 7] for i in range(61)) # period 7
for a in range(13):
for b in range(13):
for c in range(13):
assert brute_wins_subtraction((a, b, c), moves) == (g[a] ^ g[b] ^ g[c] != 0)
gs = grundy_split(40)
assert gs[:14] == [0, 0, 0, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 3]
checked = 0
for a in range(1, 15):
for b in range(a, 15):
for c in range(b, 15):
if a + b + c <= 24:
assert brute_wins_split((a, b, c)) == (gs[a] ^ gs[b] ^ gs[c] != 0)
checked += 1
assert checked == 336, checked
print("all acceptance tests passed")
# ---------------------------------------------- benchmarks
def best_of(fn, repeat=3):
best = float("inf")
for _ in range(repeat):
t0 = time.perf_counter()
fn()
best = min(best, time.perf_counter() - t0)
return best
def benchmark():
rng = random.Random(7)
print(f"{'digits':>7} {'schoolbook':>11} {'NTT':>9} {'built-in int':>13}")
for d in (100, 250, 500, 1000, 2000, 4000, 8000, 32000):
x = str(rng.randrange(10 ** (d - 1), 10 ** d))
y = str(rng.randrange(10 ** (d - 1), 10 ** d))
assert multiply_ntt(x, y) == str(int(x) * int(y))
if d <= 8000: # schoolbook at 32,000 digits takes about 30 s
assert multiply_schoolbook(x, y) == str(int(x) * int(y))
school = f"{best_of(lambda: multiply_schoolbook(x, y)):>10.4f}s"
else:
school = f"{'-':>11}"
t_ntt = best_of(lambda: multiply_ntt(x, y))
xi, yi = int(x), int(y)
t_int = best_of(lambda: xi * yi)
print(f"{d:>7} {school} {t_ntt:>8.4f}s {t_int * 1e6:>10.1f} us")
t0 = time.perf_counter()
keys = [generate_keys(1024, rng=random.Random(s)) for s in range(5)]
print(f"1024-bit key generation: {(time.perf_counter() - t0) / 5:.3f} s per key")
(n, e), (_, dd), (p, q) = keys[0]
c = encrypt_int(123456789, (n, e))
t_plain = best_of(lambda: decrypt_int(c, (n, dd)), 20)
t_crt = best_of(lambda: decrypt_crt(c, p, q, dd), 20)
print(f"decrypt 1024-bit: plain {t_plain * 1e3:.2f} ms, CRT {t_crt * 1e3:.2f} ms")
if __name__ == "__main__":
if "--bench" in sys.argv:
benchmark()
else:
run_tests()
Benchmarks and what the numbers should look like
Measured while writing this page with CPython 3.12 on an Apple-silicon Mac. Your absolute times will differ; the ratios and shapes should not.
Multiplying two -digit numbers (best of 3):
| Digits | Schoolbook (Python) | NTT (Python) | Built-in int (C, Karatsuba) |
|---|---|---|---|
| 100 | 0.2 ms | 0.4 ms | 0.2 µs |
| 250 | 1.5 ms | 0.9 ms | 0.4 µs |
| 500 | 6.9 ms | 2.2 ms | 1.8 µs |
| 1,000 | 31.6 ms | 5.0 ms | 5.4 µs |
| 2,000 | 123 ms | 10.9 ms | 16.8 µs |
| 4,000 | 513 ms | 23.4 ms | 52.0 µs |
| 8,000 | 1.95 s | 49.0 ms | 157 µs |
| 32,000 | — (about 30 s) | 225 ms | 1.47 ms |
How to read it:
- Schoolbook is quadratic: ×4 per doubling (123 → 513 → 1,954 ms). The NTT is : a bit over ×2 per doubling (10.9 → 23.4 → 49.0 ms). The crossover is around 150–250 digits; at 8,000 digits the NTT is 40× faster, and the gap keeps widening.
- The built-in is hundreds to thousands of times faster than both (312× faster than the NTT at 8,000 digits), because it is C working on 30-bit "digits" (CPython's limb size) rather than Python objects working on decimal digits. Its growth is about ×3 per doubling (52 → 157 µs; 8,000 → 32,000 digits is ×9.4 for ×4 the size, i.e. ): that is Karatsuba's . CPython has no FFT multiplication; GMP switches from Karatsuba to Toom–Cook and then to an FFT (Schönhage–Strassen) at thresholds of thousands of limbs, tuned per CPU.
- The lesson is the same as the DP capstone's: asymptotics decide the race between two implementations in the same language, constants decide it across languages. Use the built-in in production; write the NTT to understand why fast polynomial and big-number arithmetic is possible at all.
RSA.
| Operation | Time |
|---|---|
| 1,024-bit key generation (two 512-bit primes, 40 Miller–Rabin rounds on the final candidate) | 0.13 s per key (average of 5) |
| 1,024-bit decryption, plain | 3.08 ms |
| 1,024-bit decryption with the CRT | 1.25 ms (2.5× faster) |
Key generation time is dominated by the Miller–Rabin rounds spent rejecting composites (only one round is needed to reject most of them) and varies a lot from seed to seed, since the number of candidates before a prime is roughly geometric. The CRT gain is 2.5× rather than the theoretical 4× because of fixed per-call overhead in Python and the cost of the recombination step.
Extension ideas
- Signatures. Sign with where is a hash of the message, verify with . Then read why real signatures need PSS padding (RFC 8017) and why "hash then sign" without padding is forgeable.
- Three-prime NTT or a float FFT. Use base (or ) limbs, convolve modulo three NTT-friendly primes (998244353, 167772161, 469762049 are a common trio), and recombine each coefficient with the CRT (Garner's algorithm). Measure the speedup from 4× shorter transforms. Then try a complex floating-point FFT and find, experimentally, the size at which rounding errors make it wrong.
- Karatsuba in the middle. Implement Karatsuba on digit lists (Divide & Conquer) and find the two crossovers: schoolbook → Karatsuba → NTT.
- Big-integer division and square roots with Newton's method on top of your NTT multiply; then compute or to 100,000 digits.
- Deterministic Miller–Rabin for 64-bit numbers with the fixed bases {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} (see Number Theory II), and Pollard's rho to factor the toy modulus when the primes are small (try 64-bit ; then 100-bit; feel the wall).
- Batch GCD attack. Generate 1,000 keys with a deliberately broken random generator (a 16-bit seed), and recover shared primes with a product tree and remainder tree, as Heninger et al. did on real internet keys.
- Diffie–Hellman. Use a safe prime and a generator; compute shared secrets; then break a small instance with baby-step giant-step and Pohlig–Hellman when is smooth.
- Concave hulls and real data. Download a public GPS track (for example from OpenStreetMap's public GPS traces), project it, compute the convex hull, then an alpha shape or a "concave hull", and compare the areas.
- Point-in-polygon at scale. Assign 1 million random pings to 100 non-overlapping zones: brute force, then an R-tree or a grid index (Spatial Trees), and count how many polygon tests you saved.
- More games. Kayles (knock down one pin or two adjacent pins; the Grundy sequence becomes periodic with period 12 from on), Dawson's chess, or a misère version of Nim, where the XOR rule fails and your brute force should catch it. Probability (Probability & Expected Value) and counting (Combinatorics) give extra challenges: count winning positions of a given total size, or the probability that a random three-heap position is a first-player win.
- Linear algebra mod 2. Lights Out puzzles are linear systems over GF(2); solve them with Gaussian elimination (Linear Algebra) and verify by brute force on small boards.
Further reading
flowchart LR
FERMAT["Fermat test"] --> MR["Miller 1976, Rabin 1980"]
MR --> RSA["RSA 1978"]
EUCLID["Extended Euclid"] --> RSA
RSA --> PKCS["PKCS 1 v1.5, OAEP, PSS (RFC 8017)"]
FFT["Cooley-Tukey FFT 1965"] --> NTT["Pollard 1971: FFT over finite fields"]
NTT --> SS["Schoenhage-Strassen 1971"]
SS --> HVDH["Harvey-van der Hoeven 2021: O(n log n)"]
SG["Sprague 1935, Grundy 1939"] --> WW["Winning Ways 1982"]
- RSA. R. L. Rivest, A. Shamir, L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", CACM 21(2), 1978. Dan Boneh, "Twenty Years of Attacks on the RSA Cryptosystem", Notices of the AMS 46(2), 1999 — the best short tour of why textbook RSA is not secure. RFC 8017 (PKCS #1 v2.2) for OAEP, PSS and the CRT key format.
- Primality. G. L. Miller, "Riemann's Hypothesis and Tests for Primality", JCSS 13, 1976; M. O. Rabin, "Probabilistic Algorithm for Testing Primality", J. Number Theory 12, 1980; Damgård, Landrock and Pomerance, "Average case error estimates for the strong probable prime test", Math. Comp. 61, 1993.
- Fast multiplication. J. W. Cooley and J. W. Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series", Math. Comp. 19, 1965. J. M. Pollard, "The Fast Fourier Transform in a Finite Field", Math. Comp. 25, 1971. A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7, 1971. D. Harvey and J. van der Hoeven, "Integer multiplication in time ", Annals of Mathematics 193(2), 2021. The GMP manual's "Multiplication Algorithms" chapter for how a production library chooses between them. cp-algorithms.com, Fast Fourier transform (includes the NTT).
- Geometry. A. M. Andrew, "Another efficient algorithm for convex hulls in two dimensions", IPL 9(5), 1979. A. Rényi and R. Sulanke, "Über die konvexe Hülle von n zufällig gewählten Punkten", Z. Wahrscheinlichkeitstheorie 2, 1963.
- Games. R. P. Sprague, "Über mathematische Kampfspiele", Tôhoku Math. J. 41, 1935; P. M. Grundy, "Mathematics and games", Eureka 2, 1939; E. Berlekamp, J. Conway, R. Guy, Winning Ways for Your Mathematical Plays, 1982 (2nd ed. 2001–2004).
- Real-world failures. Debian Security Advisory DSA-1571-1 (2008); Heninger, Durumeric, Wustrow, Halderman, "Mining Your Ps and Qs", USENIX Security 2012; Nemec et al., "The Return of Coppersmith's Attack" (ROCA), ACM CCS 2017; Bleichenbacher, "Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1", CRYPTO 1998.
- Archon. Cryptography for Engineers · Symmetric vs Asymmetric Encryption · Key Management · Practical Cryptography · Cryptography in the real world.
Course navigation. Previous: Game Theory. Module overview: Math. Course: DSA: Zero to Mastery. Next: Module 9, Advanced Topics.