<a id="ch-01"></a>

## Chapter 1 — Calculus I

### 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](https://doi.org/10.1137/S0097539795293172)). Grover's search finds a key among 2^*k* candidates in about 2^(*k*/2) sequential iterations ([Grover 1996](https://doi.org/10.1145/237814.237866)). 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)](https://arxiv.org/abs/2505.15917) — 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

```python
# 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:

```text
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.

### Continue studying — chapter 01 of 50

[← Course home](../../README.md) · [Course chapter index](../SUBJECTS.md) · [Chapter 02 (draft) →](#ch-02)

## Worked answers

<a id="answer-ex001"></a>
**EX001.** log₂(10^30) = 30 × 3.32 ≈ 99.7 → about 100 bits. log₂(2^100 × 10^6) = 100 + 19.9 ≈ 120 bits.

<a id="answer-ex002"></a>
**EX002.** Shor's algorithm would reduce breaking RSA from an infeasible sub-exponential effort to a polynomial one — a qualitative collapse — so RSA must be replaced. Grover only square-roots the search for an AES key: AES-256 would still need about 2^128 sequential steps, which remains far out of reach. Replace RSA and elliptic curves; keep AES-256.