Why Number Theory Matters for Programmers

Number Theory & Cryptographic Math

Chapter 1 · Why Number Theory Matters for Programmers

Security's own crypto1 (Cryptography Fundamentals) and https1 (HTTPS/TLS Fundamentals) both use RSA and public-key cryptography constantly — and both, quite deliberately, never derive the actual mathematics underneath it. This course is that derivation: the specific slice of number theory that makes public-key cryptography work at all, built directly on Algorithms & Complexity's own growth-rate machinery and Discrete Mathematics Fundamentals' own proof techniques.

The Core Idea This Whole Course Builds Toward

Multiplying two numbers together is fast — genuinely, dramatically fast — no matter how large they are. Taking a large number and finding its two prime factors, with no other information to go on, is not. This asymmetry — easy to multiply, hard to factor — is not a minor curiosity. It is, quite literally, the single mathematical fact that public-key cryptography is built on top of.

Verified directly, at a small (illustrative) scale

Two primes, 887 and 997: verifying 887 is prime by trial division takes 28 divisions (up to √887 ≈ 29); verifying 997 takes 30 (up to √997 ≈ 31). Their product is 887 × 997 = 884,339 — computed in a single, trivial operation. But factoring 884,339 from scratch, with no prior knowledge of its factors, needs a trial-division search up to √884339 ≈ 940 — roughly 32× more work than checking either original prime alone, even at this tiny, three-digit scale.

Why this small demo isn't "proof" — and why that's honest

At three digits, a computer factors 884,339 instantly regardless of the ratio above — this demo illustrates the mechanism, not real-world hardness. The asymmetry becomes the actual foundation of security only once the primes involved are enormous — real RSA uses primes hundreds of digits long, where the gap between "multiply the two factors" and "factor the product with no shortcuts" stops being a curiosity and becomes computationally infeasible with any known classical algorithm. Chapter 6 builds the actual tool (primality testing) real systems use to find such primes without ever needing to factor anything.

Five Concrete Connections to Real Code

Number theory topic	Where it actually shows up
Modular arithmetic (Ch.3)	Hash table bucket indexing (`hash(key) % table_size`), circular buffers, clock/wraparound arithmetic
Modular arithmetic (Ch.3)	Checksums and error-detecting codes — the Luhn algorithm behind credit card validation, ISBN-10 and IBAN check digits
Modular exponentiation (Ch.7)	Pseudorandom number generation — classic Linear Congruential Generators run entirely on modular arithmetic
Primality testing (Ch.6)	Generating the large primes every real-world RSA key pair is built from
Everything combined (Ch.8–10)	Public-key cryptography itself — RSA key generation, encryption, and decryption, the central application this course builds toward

What This Course Won't Cover

Number theory as a full mathematical field is vast, and cryptography built on top of it is its own enormous discipline. This course deliberately covers only the specific machinery RSA needs, not a comprehensive tour of either:

A full academic number theory curriculum — algebraic number theory, analytic number theory, and the deep theory of prime distribution stay out of scope
Elliptic-curve cryptography — a genuinely different mathematical foundation (elliptic curve groups, not modular arithmetic on integers), substantial enough to deserve its own future treatment
The discrete logarithm problem in depth — Diffie-Hellman key exchange leans on modular exponentiation (Chapter 7's own topic) but its security rests on a genuinely different hard problem than RSA's factoring problem; that distinction is named honestly where it comes up, not derived in full
Post-quantum cryptography — an active, rapidly evolving research area built on entirely different mathematical foundations, out of scope for this course

Why draw the line at RSA specifically

RSA is the single cryptographic system whose entire security argument can be built, honestly and completely, from divisibility, modular arithmetic, and a handful of classical theorems — exactly what this course has room to cover in ten chapters. Everything named above is either a genuinely different mathematical foundation (elliptic curves) or would require substantially more depth than a single course allows.

Where This Course Is Headed

Chapter	Topic
2	Divisibility & the Division Algorithm
3	Modular Arithmetic
4	The Euclidean Algorithm & GCD
5	The Extended Euclidean Algorithm & Modular Inverses
6	Prime Numbers & Primality Testing
7	Modular Exponentiation & Fast Exponentiation
8	Euler's Totient Function & Fermat's Little Theorem
9	RSA: How the Math Actually Works
10	Capstone — Building a Toy RSA Implementation

This course's throughline

Every chapter adds exactly one piece a working RSA implementation genuinely needs — divisibility and remainders, working consistently under a modulus, finding a GCD efficiently, inverting under a modulus, telling whether a number is prime, exponentiating quickly under a modulus, and the two theorems that guarantee encryption and decryption actually undo each other. By Chapter 9, nothing about RSA is "magic" — it's eight prior chapters, assembled.

Hands-On Exercises

Exercise 1

Two primes, 101 and 103, are multiplied to give 10,403. Compute how many trial divisions are needed to verify 101 is prime (up to √101), and how many would be needed to factor 10,403 from scratch (up to √10403) with no prior knowledge of its factors. State the ratio between the two.

📄 View solution

Exercise 2

A colleague says "modular arithmetic is just an academic curiosity — I've never needed it in real code." Using this chapter's own five connections, name two genuinely different real systems (not variations of the same idea) that quietly rely on modular arithmetic, and explain the connection for each.

📄 View solution

Exercise 3

Using this chapter's own easy-to-multiply/hard-to-factor idea, explain in your own words why doubling the number of digits in an RSA key makes it dramatically harder to break, even though it only makes encryption and decryption modestly slower. (A precise answer isn't expected yet — Chapter 7's own fast-exponentiation material will make the "modestly slower" half exact; this exercise is about the intuition.)

📄 View solution

Chapter 1 Quick Reference

Core idea: multiplying is fast, factoring is hard — this asymmetry is the actual foundation of RSA
Verified at small scale: factoring a product from scratch needs roughly √(product) work, dramatically more than verifying either factor alone once numbers are large
Five direct connections: hash indexing, checksums/error-detecting codes, pseudorandom generation, primality testing for key generation, and RSA itself
Deliberately out of scope: a full number theory curriculum, elliptic-curve cryptography, the discrete logarithm problem in depth, post-quantum cryptography
Provides the mathematical foundation underneath Security's own crypto1 and https1 courses
Next chapter: Divisibility and the division algorithm