 There will be module assessments on:

 Wed September 20th (Module 1)
 Wed October 11th (Module 2)
 Wed November 1st (Module 3)
 Wed November 29th (Module 4)

 Final Exam Sunday December 17th, 7:30 pm
Format
My tests typically have some short answer concept type questions, e.g. true false, fill in the blank, and some longer questions where you might demonstrate how to do an algorithm or compute something.
Final Exam is cumulative
Here is the info on the portion that is new material:
 error correcting codes and their terminology (length, information rate, number of errors detected/corrected etc.)
 Hamming distance and Hamming weight
 linear codes
 decoding with syndromes (generating matrix, parity check matrix, cosets etc.)
 cyclic codes generated by a polynomial
 Reed Solomon codes
 how to correct an error with the matrix of powers of alpha
 McEliece cryptosystem (generalities, we won’t implement it)
Review problems from the chapter 18 posted on canvas: Problems 1,3,4,5 (for (c) you’ll have to look in the chapter to see what the Singleton bound is), 6, 9, 12 (for (c) you’ll have to look in the book for how to do this, but it isn’t hard), 13, 19, 20.
Wednesday, November 29th, 2023:
 single qubit state (what it is)
 Bloch sphere and standard bases: 0/1, +/, i/i
 change of basis between these various bases
 measurement (determine probabilities, collapse the state)
 Quantum Key Distribution (BB84 using the horizontal/vertical and NW/NE bases) — be able to implement any part you are tasked with
 multiple qubits; how to measure multiple qubits, either one at a time or all together
 how to detect entanglement (is a given state entangled?)
 unitary operators (definition, ability to check if a matrix is unitary)
 applying unitary operators as quantum gates to qubit states, determine the result
 big picture quantum computing concepts:
 we can compute classical functions/circuits “in parallel superposition”
 what can we compute faster than a classical computer?
 quantum fourier transform (able to write down small cases, able to compute its action on small cases)
 big picture QFT:
 what it does to periodic states and why it is useful
 how to reduce factoring to period finding (this is a classical thing)
 Shor’s periodfinding quantum algorithm:
 be able to explain the full algorithm, including the classical and quantum parts
 Basic continued fractions (just how to compute for Shor) THIS WILL HAPPEN MONDAY
Review:
 Chapter 1 of “Quantum Computation and Quantum Information” by Nielsen and Chuang (you can download the whole of Part I as a PDF from the university library here or try this link) does a good job of covering what we covered (plus a bit more)
 The overleaf notes take an even more spare/direct approach to our material, and contain a variety of exercises, including those you did for the daily post.
 I have added a section (Section 6.17) of review exercises to the overleaf notes.
OLDER TESTS
Wednesday, November 1st, 2023:
 division algorithm and gcd, extended gcd in polynomial rings over $\ZZ/p\ZZ$
 irreducible polynomials
 finite fields: definition as a quotient (modding out by an irreducible polynomial)
 listing the elements of a finite field in their simplest form and reducing more complicated expressions to these simplest forms
 ability to do arithmetic in finite fields, including making an addition or multiplication table
 number of elements in a finite field and which ones are units
 possible sizes for finite fields (we did this just as a fact)
 Finite field Fermat’s Little Theorem and the existence of a multiplicative generator (it always exists!)
 finding the inverse of an element in a finite field
 some general knowledge of the discrete logarithm in finite fields
 ability to do DH key exchange and El Gamal encryption with a finite field
 elliptic curves and their group law, can compute
 number of elements on an elliptic curve (Hasse’s theorem)
 putting an elliptic curve in projective coordinates
 elliptic curve factoring method
 discrete logarithm (DLP) on elliptic curves
 knowledge of attacks on DLP for elliptic curves (birthday/collision and babystepgiantstep work the same; no index calculus)
 turning a message into a point on an elliptic curve
 doing DiffieHellman key exchange or El Gamal encryption on an elliptic curve
 Dual_EC_DRBG (how it works and why a relationship between points is a problem)
 projective space (definition/elements over fields including finite fields)
Review:
 Miscellaneous problems in this folder.
 Poly long division: You can make up your own problems — you can divide anything by anything (remember to take coefficients mod a small prime p) — but I’ve put a few examples in the folder. How to check your answer: When you divide a by b and get quotient q with remainder r, that means a = bq + r, which is something you can check in Sage to make sure your answer is correct.
 Euclidean algorithm with polies: You can do this with any two reasonably sized polynomials (remember to take coefficients mod a small prime p), so you can make up your own problems. How to check your answer: this tool will work any polynomial extended euclidean algorithm for you showing steps! Note: it works with coefficients in the rationals by default, so at the bottom you have to pick “ring: Zn” and then set n to be your modulus, then it will work with coefficients mod n.
 Arithmetic in a finite field: you can make up your own examples by creating a finite field of whatever size you like using the first box of the Finite Fields Tool and then doing some arithmetic by hand to check. How to check your answer: You can check your work by Sage.
 Inverse in a finite field: this uses the extended euclidean algorithm, and you can make up your own by creating a finite field of whatever size you like using the first box of the Finite Fields Tool and then finding the inverse of anything nonzero. How to check your answer: You can check your work by multiplying out (on paper or in Sage).
 Adding points on an elliptic curve: there are some examples in the folder, but you can use the Elliptic Curve Tools to make up examples and then try to do them yourself. Just keep the prime small if you are working by hand. Try doing some where you add a point to itself. How to check your answer: Sage.
Wednesday, October 11th, 2023:
 greatest common divisor
 Euclidean algorithm (standard and extended)
 Inverses modulo n
 Chinese remainder theorem (many different statements, solving systems of equations, remember moduli need to be coprime!)
 computing a residue modulo nm that solves a system modulo n and m when n and m are coprime (CRT)
 Finding square roots using CRT (if you know how to factor the modulus)
 Euler phi function (and its formula)
 Fermat primality testing
 MillerRabin primality testing
 RSA cryptosystem (method, why you use an ephemeral key, basic security considerations)
 short plaintext attack on RSA
 the role of multiple square roots in factoring and Fermat factoring
 Pollard rho factoring
 Quadratic sieve factoring
 polynomial vs. exponential vs. subexponential runtimes for algorithms we’ve covered
 RSA signature (coming on Monday)
Practice problems:
 Use Fermat Primality Test and then MillerRabin Primality test on $n=561$ with base $2$. If this shows up as composite, does it give you a factor? Repeat with $n=30121$. Check your answers with Sage’s factoring method. Here are some other useful MillerRabin examples.
 Use Pollard Rho to factor $n=1111$ and $n=1189$ using $x_0=2$.
 Here’s a folder of appropriate problems grabbed from the internet. Many of the computational ones can be verified by checking your answer (figure out how!) or by comparing with Sage, but I’m happy to check anything via discord on the #checkanswers channel. You can use this channel to compare with your classmates too.
Wednesday, September 20th, 2023:
 Public and private key cryptography
 Keyspace and exhaustive search
 Cryptographic “hard problems”
 computational complexity:
 Big Oh notation
 runtime analysis of algorithms
 polynomial, subexponential, exponential
 Classical cryptosystems:
 substitution ciphers,
 affine cipher including cryptanalysis,in:spam
 modular arithmetic:
 computations
 reducing summands and factors but not exponents
 no cancellation (unless invertible)
 equivalent conditions for invertibility
 set of invertible elements $(\mathbb{Z}/n\mathbb{Z})^*$ (definition and computation)
 euler’s phi function, definition and formula
 linear algebra mod n (invertibility of matrices)
 efficient exponentiation (successive squaring)
 multiplicative order (definition and computation)
 Fermat/Euler theorems
 Using Fermat/Euler to tackle $a^{b^c}$ style problems
 primitive roots (definition)
 Computational DiffieHellman problem
 Discrete logarithm problem
 DiffieHellman key exchange
 Babystep giant step (including runtime)
 Index calculus (excluding runtime)
 El Gamal Cryptosystem (including what happens if you reuse the ephemeral key)
For some review problems, I’ve posted a folder of exercises and examples here. Solutions are not included, but for computations, they can generally be verified by Sage. Do not hesitate to reach out to me on discord to check work.