Chapter 1 — Calculus I
Lesson map
Lesson 01 published. Map, example, EX001.
flowchart TD
N0["Learning outcomes"]
N1["1.1 Why an engineer needs growth rates"]
N2["1.2 Logarithms and bits of security"]
N3["1.4 Practical activity — Lab G"]
N4["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4
N4 --> EX["Worked example"]
EX --> Q["Exercise EX001"]
Logical drawing
flowchart LR
N0["Learning outcomes"]
N1["1.1 Why an engineer needs growth rates"]
N2["1.2 Logarithms and bits of security"]
N3["1.4 Practical activity — Lab G"]
N4["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX001"]
[Learning outcomes]
|
v
[1.1 Why an engineer needs growth rates]
|
v
[1.2 Logarithms and bits of security]
|
v
[1.4 Practical activity — Lab G]
|
v
[Synthesis]
|
v
[Worked example] --> [Exercise EX001]
Learning outcomes
You will (1) compare growth rates — polynomial, sub-exponential and exponential — and explain why they decide what a quantum computer threatens; (2) use logarithms to convert work factors into "bits of security"; and (3) read an asymptotic claim critically. This chapter starts the foundations stage and prepares the discrete mathematics of Chapter 2.
1.1 Why an engineer needs growth rates
Every security claim in this book is a claim about how fast some cost grows. Brute-forcing a k-bit key takes about 2^k trials: the cost doubles with each extra bit, which is exponential growth. The best classical factoring algorithm, the general number field sieve, runs in sub-exponential time, roughly exp(c·(ln N)^(1/3)·(ln ln N)^(2/3)) for a modulus N. Shor's algorithm factors in time polynomial in the number of bits — on the order of n³ elementary quantum gates for an n-bit modulus, ignoring error-correction overhead (Shor 1997). Grover's search finds a key among 2^k candidates in about 2^(k/2) sequential iterations (Grover 1996). The whole PQC story follows from these four functions: Shor turns a sub-exponential problem into a polynomial one, which is catastrophic for RSA and elliptic curves; Grover only halves the exponent, which is why AES-256 remains acceptable.
1.2 Logarithms and bits of security
Taking log₂ of a work factor gives "bits of security". A cost of 2^128 operations is "128-bit security". Logarithms turn products into sums, so doubling the work adds one bit, and multiplying it by a million (≈2^20) adds about twenty bits. This is why engineers say a 2^20 speed-up from better hardware "costs" twenty bits. The derivative helps intuition: the GNFS cost curve flattens in bits as keys grow, so each extra RSA bit buys less security than each extra AES bit — one reason RSA keys are thousands of bits long.
1.3 Limits and asymptotic notation
"Big-O" statements describe behaviour as input size tends to infinity and hide constants. Shor's n³ hides a large constant and, more importantly, the overhead of quantum error correction, which may multiply physical qubit counts by a thousand or more. Resource estimates such as Gidney (2025) — under one million noisy qubits for RSA-2048 under stated hardware assumptions — fill in those constants. An engineer must never read an asymptotic bound as a time.
Two algorithms with the same big-O can differ by factors that decide whether an attack takes an hour or a decade. The jump from twenty million noisy qubits to under a million came from better constants and codes, not from a change in Shor's n³. When a vendor quotes an asymptotic bound, the engineer asks for the hardware assumptions behind the constant.
1.4 Practical activity — Lab G
# Lab G (ch 1): growth rates that decide what quantum computers threaten.
import math
print("Symmetric key search: classical 2^k trials vs Grover ~2^(k/2) sequential iterations")
for k in (128, 192, 256):
print(f" k={k}: classical 2^{k}, Grover ~2^{k//2}")
def gnfs_bits(n_bits): # heuristic L_N[1/3, (64/9)^(1/3)] work, expressed in bits
ln_n = n_bits * math.log(2)
work = (64/9) ** (1/3) * ln_n ** (1/3) * math.log(ln_n) ** (2/3)
return work / math.log(2)
print("Factoring an n-bit RSA modulus: classical GNFS (heuristic) vs Shor gate count ~n^3")
for n in (1024, 2048, 3072):
print(f" n={n}: GNFS ~2^{gnfs_bits(n):.0f} operations; Shor ~n^3 = 2^{math.log2(n**3):.0f} logical gates")
Expected output:
Symmetric key search: classical 2^k trials vs Grover ~2^(k/2) sequential iterations
k=128: classical 2^128, Grover ~2^64
k=192: classical 2^192, Grover ~2^96
k=256: classical 2^256, Grover ~2^128
Factoring an n-bit RSA modulus: classical GNFS (heuristic) vs Shor gate count ~n^3
n=1024: GNFS ~2^87 operations; Shor ~n^3 = 2^30 logical gates
n=2048: GNFS ~2^117 operations; Shor ~n^3 = 2^33 logical gates
n=3072: GNFS ~2^139 operations; Shor ~n^3 = 2^35 logical gates
The GNFS formula is heuristic (its o(1) term is dropped), so the bit values approximate the commonly quoted 112-bit strength of RSA-2048 rather than match it. The Shor "gate counts" are logical gates before error correction.
The lab's comparison exists to make the shapes visible side by side: brute force doubles per bit, GNFS bends more slowly, and Shor's logical gate count grows only polynomially. Running it for 1024, 2048 and 3072-bit moduli shows why longer RSA keys buy little against a quantum adversary. Students should annotate their table with the warning that the Shor column omits error-correction overhead, so no row should be read as a time to break.
1.5 Worked example: BPA's first question
BPA's board asks whether to double AES key sizes "because of quantum". Using 1.1: AES-128 under Grover falls to roughly 2^64 sequential iterations in the idealized model, but Grover parallelizes poorly, so many guidance documents still accept AES-128; moving bulk encryption to AES-256 is cheap and removes the debate. The urgent item is not AES but every RSA and elliptic-curve key exchange, which Shor breaks outright.
The memo to BPA's board therefore separates two decisions. Symmetric keys move to AES-256 during normal refresh, at almost no cost. Key exchange and signatures need a planned migration to ML-KEM and ML-DSA, because no key length rescues RSA or elliptic curves from Shor. Mixing the two questions is how boards spend money on the cheap fix and delay the important one.
1.6 Common errors and limits
- Treating Grover as fatal to symmetric cryptography.
- Reading O(n³) as "fast" without error-correction overhead.
- Comparing bits across exponential and sub-exponential curves as if they grew alike.
Each error leads to a wrong decision. Treating Grover as fatal sends budget to symmetric upgrades that were already adequate. Reading n³ as fast ignores the physical qubits needed for each logical one. Comparing bit numbers across different growth curves makes RSA-3072 look stronger against quantum attack than it is. The models in this chapter compare options; they are not schedules.
Exercises
- EX001 — Bits from work. Convert 10^30 and 2^100 × 10^6 operations into bits of security. Rubric: 3 = both correct with method.
- EX002 — Explain the asymmetry. In 150 words, explain to BPA's board why RSA must be replaced but AES-256 need not. Rubric: 3 = growth-rate argument correct and non-technical.
Synthesis
Growth rates decide everything: Shor makes factoring and discrete logarithms polynomial; Grover merely square-roots search. Bits of security are logarithms of work, and asymptotic bounds need resource estimates before they mean time.