The following calendar will be populated with links to worksheets, videos, and activities, so you can catch up on anything you’ve missed and revisit important material.
Monday, August 26th, 2024:
- Whirlwind Tour of Cryptography, as an intro to the course (Part I). Here are the slides I am using.
Wednesday, August 28th, 2024:
- Finished the whirlwind tour (slides) and reviewed modular arithmetic / daily post.
- Lecture notes.
Friday, August 30th, 2024:
- Took up daily post (solutions in the lecture notes below).
- We covered inverses in modular arithmetic, why they matter to affine cipher, Hill cipher, some review of functions (injective, surjective, bijective, injective).
- Lecture notes.
Wednesday, September 4th, 2024:
- We took up daily post and discussed successive squaring, invertibility, gcd, unit group and euler phi function.
- Lecture notes.
Friday, September 6th, 2024:
- We discussed euler phi function, multiplicative group, dynamical portraits, Fermat’s little theorem, Euler’s theorem. Think cycles!
- Lecture notes.
Monday, September 9th, 2024:
- Using Euler’s theorem to do exponents on exponents etc. (modular arithmetic practice)
- Review of our modular arithmetic for multiplicative group and the big cycle we want
- Diffie-Hellman Key Exchange and its hard problems, and naive approaches to these
- Lecture notes (cobbled-together not exactly what we did in class)
Wednesday, September 11th, 2024:
- Euclidean algorithm and extended euclidean algorithm
- Dr. Stange’s lecture notes (provided to Dr. Luh)
- Dr. Luh’s notes
Friday, September 13th, 2024:
- Sunzi’s Theorem (Chinese Remainder Theorem)
- modular inverses
- Dr. Stange’s lecture notes (provided to Dr. Luh)
- Dr. Luh’s notes
Monday, September 16th, 2024:
- El Gamal Encryption and why ephemeral keys
- Review (example of CRT)
- Lecture Notes
- Sunzi demo
Wednesday, September 18th, 2024:
- Test #1
- Solutions
Friday, September 20th, 2024:
- Joseph Macula substituted
- Runtimes and Big-O notation
- Basic definitions of discrete logs
- Lecture notes I gave the TA (may not match class exactly)
Monday September 23rd, 2024:
- Discrete logs and Baby-Step Giant-Step
- Lectures notes
Wednesday September 25th, 2024:
- Index Calculus algorithm
- Lecture notes
Friday September 27th, 2024:
- Birthday Paradox
- RSA Encryption
- Lecture notes
Monday September 30th, 2024:
- timing attacks, number of primes
- Lecture notes
Wednesday October 2, 2024:
- Fermat primality test
- notion of “probably prime”
- Principle of Multitudinous Square Roots
- Intro to Quadratic Sieve
- Lecture notes
Friday October 4th, 2024:
- Finish quadratic sieve
- Miller-Rabin primality testing
- birthday attacking small messages in RSA
- Lecture notes
Monday October 7th, 2024:
- RSA signature
- hash functions
- Lecture notes
Wednesday October 9th, 2024:
Friday October 11th, 2024:
- elliptic curves!
- Lecture notes
- A lecture recording from last year’s class is here (requires login).
Monday, October 14th, 2024:
- projective space
- number of points on an elliptic curve
- Lecture notes: presentation and notes.
Wednesday, October 16th, 2024:
- elliptic curve factoring
- Lecture notes
Friday, October 18th, 2024:
- Elliptic Curve Discrete Log Problem
- Elliptic Curve Diffie Hellman
- Elliptic Curve El Gamal
- Lecture notes
Monday, October 21st, 2024:
- Pseudo-random number generators, Dual_EC_DRBG, square roots mod p
- Lecture notes
Wednesday, October 23rd, 2024:
- Complex numbers
- Qubits
- Measurement
- L and V bases for polarization and the filter demo
- Lecture notes
- This was an important class not to miss: here’s last year’s corresponding video (UCB login)
Friday, October 25th, 2024:
- Quantum Key Exchange
- Lecture Notes
Monday, October 28th, 2024:
- Two qubit systems and entanglement
- Lecture Notes
Wednesday, October 30th, 2024:
Friday, November 1st, 2024:
- Quantum gates
- This is a tough class to have missed. Start this video at time stamp 38:38 for a catch up of the material.
- Lecture Notes
Monday, November 4th, 2024:
- Reversibility & making classical circuits reversible
- Massive parallelism
- Introduction to vector space of functions
- Lecture Notes
Wednesday, November 6th, 2024:
- Quantum Fourier Transform
- Lecture Notes
Friday, November 8th, 2024:
- Shor’s algorithm
- Lecture Notes
Monday, November 11th, 2024:
- Continued fractions
- Finish Shor’s algorithm (w/ example)
- Lecture Notes
Wednesday, November 13th, 2024:
- Introduction to Lattices (bases, change of basis, hard problems)
- Lattice reduction in 2D
- Desmos Demo
- Lecture Notes
Friday, November 15th, 2024:
- Regev Encryption and the Learning-With-Errors Problem
- unfortunately, I don’t have a similar recording in my archive
- I will try to add an extended narrative to the overleaf notes
- Lecture Notes
Monday, November 18th, 2024:
- Some big-picture things about lattices (LLL, state of the art, Ring-LWE)
- Some intuition on vector spaces over finite fields via Tic Tac Toe
- Lecture Notes
Wednesday, November 20th, 2024:
Friday, November 22nd, 2024:
- Intro to Coding Theory.
- Lecture Notes
Monday, December 2nd, 2024:
- Linear codes
- Lecture Notes
Wednesday, December 4th, 2024:
- Linear codes and cyclic codes
- Lecture Notes
Friday, December 6th, 2024:
- Poster presentations
Monday, December 9th, 2024:
- Poster presentations
Wednesday, December 11th, 2024: