Tests

  • 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 period-finding 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 baby-step-giant-step work the same; no index calculus)
  • turning a message into a point on an elliptic curve
  • doing Diffie-Hellman 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 non-zero.  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
  • Miller-Rabin 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:

  1. Use Fermat Primality Test and then Miller-Rabin 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 Miller-Rabin examples.
  2. Use Pollard Rho to factor $n=1111$ and $n=1189$ using $x_0=2$.
  3. 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 #check-answers 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 Diffie-Hellman problem
  • Discrete logarithm problem
  • Diffie-Hellman key exchange
  • Baby-step giant step (including runtime)
  • Index calculus (excluding runtime)
  • El Gamal Cryptosystem (including what happens if you re-use 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.