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.

Five Concrete Connections to Real Code

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

Where This Course Is Headed

Hands-On Exercises

Everything in this course — modular arithmetic, the Euclidean algorithm, RSA itself — is ultimately built from one small idea: what does it actually mean for one whole number to divide another, and what can be guaranteed about the leftover when it doesn't divide evenly?

Divisibility, Defined Precisely

An integer a divides an integer b — written a | b — if there exists some integer k such that b = a × k. Read a | b as "a divides b," never as a fraction. 3 | 12 because 12 = 3 × 4; 5 ∤ 12 (5 does not divide 12) because no integer k makes 5k = 12.

The Division Algorithm: A Guarantee, Not Just an Operation

For any integer a (the dividend) and any positive integer d (the divisor), there exist unique integers q (quotient) and r (remainder) such that:

The uniqueness is what makes this a genuine theorem rather than just a description of long division — r is pinned down precisely by the requirement 0 ≤ r < d, ruling out every other way of splitting a into a multiple of d plus a leftover.

Classic Divisibility Rules

Quick tests for divisibility by small numbers, without doing a full division — genuinely useful shortcuts, and a nice warm-up before the heavier machinery in later chapters:

Properties of Divisibility (Needed Later)

Three properties, each provable directly from the definition above (exactly the direct-proof style Discrete Mathematics Fundamentals built), that later chapters lean on without re-deriving:

• If a | b and a | c, then a | (b + c) and a | (b − c)
• If a | b, then a | (bc) for any integer c
• If a | b and b | c, then a | c (transitivity)

Why This Is the Foundation Everything Else Builds On

Chapter 3's entire subject — modular arithmetic — is literally "take the division algorithm's own remainder, and build an entire arithmetic system that only ever tracks that remainder." Chapter 4's Euclidean algorithm is nothing more than the division algorithm, applied over and over. Every % operator in every programming language is a direct, real-world implementation of the guarantee stated in this chapter.

The Division Algorithm in Code

Hands-On Exercises

Chapter 2 built the division algorithm and treated the remainder r as a byproduct — something left over after the "real" answer, the quotient. Modular arithmetic flips that entirely: the remainder is the whole answer, and the quotient is thrown away. Everything from here to RSA itself is built on that single reframing.

Congruence: "Same Remainder" as an Equals Sign

Two integers a and b are congruent modulo n — written a ≡ b (mod n) — if they leave the same remainder when divided by n, which is exactly equivalent to saying n | (a − b).

Addition, Subtraction, and Multiplication All "Just Work"

The single most useful practical fact in this entire chapter: you can reduce modulo n at any point during a computation — before, during, or after — without ever changing the final answer modulo n.

This is not a minor convenience — it's the entire reason modular exponentiation (Chapter 7) is computationally feasible at all for the enormous numbers RSA actually uses: intermediate values never need to grow beyond the modulus itself, no matter how large the final unreduced answer would otherwise be.

Division Doesn't Work the Same Simple Way

Addition, subtraction, and multiplication all reduce cleanly under a modulus. Division does not have an equally simple counterpart — there's no general rule like (a ÷ b) mod n = ((a mod n) ÷ (b mod n)) mod n, because ordinary division isn't guaranteed to produce a whole number, and modular arithmetic only deals in integers.

A Real Cross-Language Gotcha: What % Actually Does With Negative Numbers

Chapter 2 already flagged this once — now it matters directly. Programming languages genuinely disagree about what % returns for a negative operand:

Real Relevance: Clocks, Weekdays, and Wraparound

A 12-hour clock is arithmetic modulo 12; days of the week cycle modulo 7; a circular buffer's write position wraps modulo its own capacity. Any time a quantity needs to "wrap around" back to the start after reaching a fixed limit, that's modular arithmetic, whether or not the code ever calls it that.

Modular Arithmetic in Code

Hands-On Exercises

Chapter 3 closed with a gap: division doesn't reduce simply under a modulus, and closing that gap needs a modular inverse. Building a modular inverse needs the extended Euclidean algorithm (Chapter 5) — and that, in turn, is built directly on top of the plain Euclidean algorithm this chapter covers: the single fastest known way to find the greatest common divisor of two numbers.

GCD, and Why the Obvious Approach Doesn't Scale

The greatest common divisor of a and b — gcd(a, b) — is the largest positive integer that divides both. The obvious approach: check every integer from min(a,b) down to 1, stopping at the first one that divides both. That works, but it needs up to min(a,b) checks — for the hundreds-of-digit numbers RSA actually uses, that's not slow, it's completely infeasible, worse than any brute-force approach Algorithms & Complexity ever flagged as impractical.

The Key Identity: gcd(a, b) = gcd(b, a mod b)

This is the entire algorithm, and it's not a shortcut or an approximation — it's an exact equality, provable directly from Chapter 2's own divisibility properties, not asserted on faith.

The Algorithm, Traced

Repeatedly replace (a, b) with (b, a mod b) until b reaches 0 — at that point, a is the GCD (the base case: gcd(a, 0) = a).

Why It Terminates So Quickly

Each step replaces the larger number with a strictly smaller remainder — Algorithms & Complexity's own recursion-analysis machinery applies directly. It's a provable fact (not covered in depth here, but well established) that the remainder more than halves every two steps in the worst case, giving the algorithm O(log(min(a,b))) steps overall — logarithmic in the size of the input, not linear.

Real Relevance

Beyond reducing fractions to lowest terms, this exact algorithm is the direct foundation Chapter 5's extended Euclidean algorithm builds on to compute modular inverses — and RSA key generation itself runs a GCD check (gcd(e, φ(n)) = 1, Chapter 8) to confirm a chosen encryption exponent is actually usable, every single time a key pair is generated.

The Euclidean Algorithm in Code

Hands-On Exercises

Chapter 4 built the Euclidean algorithm to find a number — the GCD. This chapter extends it to find something far more useful: two numbers that combine to produce that GCD. That small extension is the entire tool needed to close the gap Chapter 3 left open — dividing under a modulus.

Bézout's Identity

This isn't just a useful trick — it's a genuine guarantee that a specific linear combination of a and b always exists and always lands exactly on their GCD, never anything smaller.

The Extended Euclidean Algorithm: Finding x and y

Run the same division steps as Chapter 4, but track two extra running values (s and t) at every step, each starting from the trivial coefficients of a and b themselves, updated by the same quotient used to update the remainder.

Modular Inverses: What Bézout Actually Unlocks

A number a has a modular inverse mod n — a number a⁻¹ such that a × a⁻¹ ≡ 1 (mod n) — if and only if gcd(a, n) = 1 (a and n are coprime).

When No Inverse Exists

If gcd(a, n) ≠ 1, no modular inverse exists at all — not "hard to find," genuinely absent.

Real Relevance: This Is Literally RSA's Private Key

Chapter 9 computes RSA's private decryption exponent as d = e⁻¹ mod φ(n) — a modular inverse, found using exactly the algorithm in this chapter. Key generation deliberately chooses e to be coprime with φ(n) specifically so this inverse is guaranteed to exist — the gcd = 1 condition from this chapter is a real, load-bearing constraint on how RSA keys are generated, not a footnote.

The Extended Euclidean Algorithm in Code

Hands-On Exercises

Chapter 5's modular inverses need gcd(a, n) = 1. The cleanest way to guarantee that is to build n out of prime numbers — and RSA does exactly this. This chapter builds the actual tool real systems use to find primes large enough for cryptography.

What a Prime Actually Is

A prime is an integer greater than 1 whose only positive divisors are 1 and itself. 1 is deliberately excluded by definition — if it counted as prime, numbers wouldn't have a single unique prime factorization (12 = 2×2×3 could also be written 1×2×2×3, 1×1×2×2×3, and so on, endlessly).

Trial Division, Formalized

Chapter 1's own finding-box already used trial division informally. Here's why checking only up to √n is enough, not just a shortcut:

The Sieve of Eratosthenes: Finding Many Primes at Once

Trial division checks one number. To find every prime up to some limit, the Sieve of Eratosthenes is dramatically more efficient: starting from 2, cross out every multiple of each prime found, moving upward.

Trial division is the right tool for checking a single already-chosen candidate; the sieve is the right tool for finding many small primes at once — genuinely different jobs, not competing solutions to the same problem.

Why Neither Tool Works at RSA Scale

Probabilistic Primality Testing: Trading Certainty for Speed

Instead of proving primality with total certainty, a probabilistic test checks a property that every prime satisfies, but which most composite numbers fail. A candidate that passes many independent rounds is declared "probably prime," with a failure probability that can be made astronomically small — smaller than the odds of an undetected hardware error corrupting the computation itself.

Why a Single Test Isn't Enough: A Real Counterexample

Real Relevance

Every real-world crypto library — the ones underneath Security's own crypto1 and https1 — generates RSA primes by sieving out small factors quickly, then running many rounds of a probabilistic test (Miller-Rabin in practice) on the survivors. Nothing here is a simplification for teaching purposes; this is genuinely how production key generation works.

Primality Testing in Code

Hands-On Exercises

Chapter 6's code quietly used Python's built-in three-argument pow(a, b, n) without explaining how it computes aᵇ mod n so fast even when b is astronomically large. This chapter opens that box — and the answer turns out to be a direct, concrete payoff of Algorithms & Complexity's own recursion and growth-rate machinery.

The Naive Approach, and Why It Can't Scale

The obvious way to compute aᵇ mod n: multiply by a, one step at a time, b times, reducing mod n along the way. That's O(b) multiplications — linear in the exponent itself, not the number of digits in the exponent.

Fast Exponentiation: Square-and-Multiply

The fix reuses the exact same halving idea behind Algorithms & Complexity's own T(n) = T(n/2) + O(1) recurrence: aᵇ can always be built from a^(b/2), squared — halving the exponent at every step instead of decrementing it by one.

In practice, this is implemented iteratively by walking through b's own binary digits — squaring a running base value at every step, and multiplying it into the running result exactly when the current bit is 1.

The Gap, at Real Scale

All values verified directly. At real RSA scale (b = 2²⁰⁴⁸, a number with a single bit set among its 2,049 binary digits), fast exponentiation needs one squaring per bit position plus one extra multiply for that single set bit — 2,049 + 1 = 2,050 total, matching the verified count exactly. A computation any modern computer finishes in milliseconds, for a naive approach that would never finish at all.

The Other Half of the Trick: Reduce After Every Multiplication

Fast exponentiation alone isn't enough — Chapter 3's own reduce-anytime property has to be applied at every single step, not just at the end, or the raw numbers explode before the exponent ever finishes shrinking.

Real Relevance: This Is Literally How RSA Encrypts and Decrypts

Chapter 9 defines RSA encryption as c = mᵉ mod n and decryption as m = cᵈ mod n — both are modular exponentiations, computed with the exact algorithm in this chapter, on numbers hundreds of digits long. Fast exponentiation isn't an optimization RSA happens to use — it's the specific reason RSA is fast enough to be usable at all.

Fast Modular Exponentiation in Code

Hands-On Exercises

Every prior chapter built a tool: the division algorithm, modular arithmetic, the Euclidean algorithm, modular inverses, primality testing, fast exponentiation. This chapter builds the last piece of pure theorem — the actual mathematical fact that makes RSA's encryption and decryption genuinely undo each other, not just a fact stated on faith.

Euler's Totient Function: Counting Coprimes

Euler's totient function, φ(n), counts how many integers in [1, n] are coprime to n — that is, how many satisfy gcd(k, n) = 1.

Fermat's Little Theorem, Proved — Not Just Stated

Chapters 6 and 7 both used this without proof. Here's the actual argument, built entirely from tools this course has already established:

This is a genuine direct proof, in the same style Discrete Mathematics Fundamentals established — no step taken on faith, and the final cancellation step is literally Chapter 5's own modular inverse doing real work.

Euler's Theorem: The Generalization to Any Modulus

The exact same permutation argument works, replacing "all of 1 to p−1" with "everything in [1,n] coprime to n" — that set has φ(n) elements by definition, and multiplying by any coprime a still just rearranges it. Fermat's Little Theorem is the special case where n happens to be prime (since φ(p) = p−1).

Real Relevance: This Is RSA's Actual Correctness Argument

Chapter 9 sets n = pq, uses φ(n) = (p−1)(q−1) (this chapter's own formula), and chooses e and d so that ed ≡ 1 (mod φ(n)) — a modular inverse, Chapter 5's own tool. Euler's theorem then guarantees m^(ed) ≡ m (mod n) for any message m coprime to n — the entire reason decrypting an RSA-encrypted message recovers the original message. Nothing about that guarantee is new material — it's this chapter's own theorem, applied.

Totient & Fermat's Little Theorem in Code

Hands-On Exercises

No new mathematics appears in this chapter. Every tool RSA needs was already built — divisibility (Ch.2), modular arithmetic (Ch.3), the Euclidean algorithm (Ch.4), modular inverses (Ch.5), primality testing (Ch.6), fast exponentiation (Ch.7), and Euler's theorem (Ch.8). This chapter is pure assembly.

Key Generation, Step by Step

Encryption and Decryption

Why It Works: The Actual Proof, Not an Assertion

By construction (step 5), ed ≡ 1 (mod φ(n)) — meaning ed = 1 + kφ(n) for some integer k. Decrypting an encrypted message:

Security: Why Factoring n Breaks Everything

Anyone who can factor the public n back into p and q can recompute φ(n) = (p−1)(q−1) directly, then run Chapter 5's own extended Euclidean algorithm to compute d exactly as the key's own owner did — completely breaking the private key. This is Chapter 1's own multiply-vs-factor asymmetry, made concrete: n is public precisely because computing it from p and q is instant, while the reverse — factoring n back into p and q — is (for large enough primes) computationally infeasible with any known method. Every piece of this course has been building toward exactly this one sentence.

Toy RSA in Code

Hands-On Exercises

One continuous project, touching every chapter of this course in the order a real implementation actually needs them: generate real primes, build a real key pair, encrypt and decrypt a real word, measure the real cost of doing it the slow way versus the fast way — then, finally, sit in the attacker's seat and try to break the exact system just built.

Step 1 — Generate and Verify Two Real Primes

Step 2 — Compute the Modulus and Totient

Step 3 — Choose a Valid Public Exponent

Step 4 — Compute the Private Exponent

Steps 5-6 — Encrypt and Decrypt a Real Word

Step 7 — Fast Exponentiation's Real Payoff, on This Exact Key

Step 8 — The Security Audit: Try to Break What Was Just Built

What This Course Doesn't Cover

As stated honestly back in Chapter 1: a full academic number theory curriculum, elliptic-curve cryptography, the discrete logarithm problem in depth, and post-quantum cryptography were all named as deliberately out of scope, and stayed out of scope through all ten chapters. This course built the specific number-theoretic machinery RSA needs — divisibility, modular arithmetic, GCDs, modular inverses, primality, fast exponentiation, and the totient/Fermat/Euler theorems — not an exhaustive tour of either field.

Where This Course Connects

This course is the mathematical foundation underneath Security's own crypto1 (Cryptography Fundamentals) and https1 (HTTPS/TLS Fundamentals), both of which use RSA and public-key cryptography operationally without deriving the number theory behind them — this course is that derivation, made concrete on real (if small) numbers throughout. Algorithms & Complexity's own growth-rate and recursion machinery was used directly in Chapters 4 and 7; Discrete Mathematics Fundamentals' own direct-proof style was the template for Chapter 8's Fermat's Little Theorem proof.

Hands-On Exercises