1
Run the algorithms by hand
Division, Euclid, extended Euclid, fast exponentiation. Each with its trace, so the method transfers to paper.
Course · Discrete Mathematics
Number Theory and Cryptography
Everything follows from one theorem about division with remainder. Primes, gcds, congruences and modular inverses build up to RSA — which is generated, used and then broken here on primes small enough to check by hand.
a = qb + r, 0 ≤ r < b unique q and r
gcd(a,b) = ax + by Bézout
a^{p−1} ≡ 1 (mod p) Fermat, for prime p ∤ a
ed ≡ 1 (mod φ(n)) ⟹ m^{ed} ≡ m (mod n) RSA
What this course is about
- Subject
- Discrete Mathematics
- Lessons
- 14
- Format
- Interactive
Overview
What you will be able to do
By the end you can compute in modular arithmetic confidently, judge the parameters of the everyday systems built on it, and explain exactly what RSA's security rests on.
2
Solve congruences
Decide solvability, count the solutions, and find them — including simultaneous systems by the Chinese remainder theorem.
3
Use Fermat and Euler
Reduce enormous exponents to small ones, and know exactly which hypotheses each theorem needs.
4
Explain RSA honestly
Generate a key, encrypt and decrypt, and then recover the private key by factoring — which is what shows what the security actually depends on.
5
Judge an application's parameters
Choose a hash modulus and say why a power of two fails, check the three conditions that give a generator full period, and validate an affine key — then break one from two letter frequencies.
Lessons
14 lessons
Divisibility and gcd come first, then modular arithmetic, and last the applications that use all of it.
Divisibility and the Division AlgorithmEvery division leaves a unique quotient and remainder.Not marked
Primes and Unique FactorisationEvery integer above 1 factors into primes, in exactly one way.Not marked
The Sieve of EratosthenesCross out the multiples; what survives is prime.Not marked
Greatest Common DivisorThe largest number dividing both, and how not to find it.Not marked
The Euclidean AlgorithmReplace (a, b) by (b, a mod b) until the remainder is zero.Not marked
Bézout's Identity and Modular InversesThe gcd is a linear combination — and that gives inverses.Not marked
Modular ArithmeticArithmetic on remainders, and why it is well defined.Not marked
Modular ExponentiationCompute aᵇ mod m without ever forming aᵇ.Not marked
Linear Congruencesax ≡ b (mod m): solvable exactly when gcd(a,m) divides b.Not marked
The Chinese Remainder TheoremSimultaneous congruences with coprime moduli have exactly one solution.Not marked
Fermat's Little Theorem and Euler's TheoremExponents reduce modulo φ(m), not modulo m.Not marked
Hashing and Pseudorandom NumbersTwo everyday uses of modular arithmetic.Not marked
Classical CiphersShift, affine and Vigenère — and why each one falls.Not marked
RSA EncryptionPublic-key encryption from Euler's theorem — and what its security rests on.Not marked
Recommended background
Proof technique and induction.
Practice suggestions
Use the workbench lab in every lesson. Each mode prints the algorithm's trace rather than only its answer, and the point is to be able to reproduce the trace on paper afterwards. Every lab opens on its own lesson's example, so the first figure on the screen is one the text above it already states; change one input and watch which lines move.
Do the RSA lesson with the primes it starts with, then change them. Watching the key change and the ciphertext change with it is what makes the mechanism concrete.
Take the factoring demonstration in “RSA Encryption” seriously. The lab breaks the key it just generated, and understanding why that is easy here and hard in practice is the whole security argument.
What it does not cover
Analytic number theory: the prime number theorem is quoted in “The Sieve of Eratosthenes” and not proved, and the Riemann hypothesis is mentioned only as context.
Elliptic curves, discrete logarithms and Diffie–Hellman. RSA is the one public-key system developed here.
Cryptographic engineering: padding schemes, key management, side channels and protocol design. “RSA Encryption” is the mathematics of RSA, and textbook RSA is not a system anyone should deploy.