So many admin announcements this time of year! Please read back through the last 4 daily posts to make sure you didn’t miss anything.
Written retakes are due on canvas by the exam. (Tests 1-3)
I’d love it if you could provide some feedback on the poster assignment (my first time doing it this year) and other aspects of the course: two question anonymous survey here: https://forms.gle/fncVHARYpbxznJHL8 (optional but appreciated).
Please do your FCQs also!
Now a few review problems. Do you remember Sunzi/Chinese Remainder? Try out this Chinese Remainder Theorem problem, by hand: x = 3 mod 214 and x = 11 mod 495. Show all the steps of the process, including the extended euclidean algorithm. You can use the computer to do modular arithmetic for you (e.g. multiplying things if needed), but show the steps as if doing it by hand.
Now, use Sunzi to find all the square roots of 3 modulo 143. There should be 4. Hint: you can break 143 = 13*11.
Now use Sunzi to find all the square roots of 33 modulo 143. There should be none (why?).
Can you create a similar example with 1 square root. With 2?
Please do your FCQs! Please go back two daily posts and check all the end-of-semester announcements on that post. Make sure you are ready to hand in your self-eval sheet.
Note: there was a typo in the solutions (not exam) for Test #2, the baby-step-giant-step problem. I don’t think there was any grading error as a result of this, but if you are concerned, please re-download the file from the website and check. It has now been fixed in the solutions set.
Test #4 solutions are up (Archive tab).
Written replacement problems are up on canvas — the PDF of the replacement problems is on the corresponding dropbox page. Reminder: you can replace one computational problem on each of the first three tests. If you wanted to replace a score of 6 or below, that was in person; but for scores 7 and above, you can do a written replacement, due on exam day (I extended the deadline), so it can be helpful for studying.
The final videos (last day) are up (they are on the Archive tab above), and they cover two aspects of coding theory. One is finishing up the cyclic codes were were discussing. The other is the McEliece post-quantum cryptosystem. I will not ask you to do computational McEliece, just to understand the general idea (what is the hard problem? what is the secret and public key? etc — I won’t quiz you on the exact equations either).
As I’ve mentioned, between now and the exam, I will take requests for further material demonstrating review problems, answering questions, reviewing topics, etc., just be specific please. Please specify if you’d like me to write up something in the textbook or make a video. I’ll do as many as I can, as a compensation for my physical unavailability during the last week before the exam. I’ll also try to be responsive on discord, but I’m going to be in New Zealand so keep in mind I might be sleeping while you’re awake! Your TA will proctor the final.
If you are having any special circumstances for the final, e.g. extra time, please make sure you know *when* and *where* you need to be. Contact me if you are unsure.
For Monday, here are some early-semester review problems to get you rolling for the final:
Find the GCD of 27 and 79.
Solve 27x + 79y = 1 using the extended euclidean algorithm.
Compute 2^27 modulo 19 using successive squaring.
Explain how you can tell 5 is invertible modulo 191.
Find the inverse of 5 modulo 191 (this uses extended euclidean).
Please review/revisit the last post for end-of-term notifications and make sure everything is in place for you and you aren’t missing and deadlines or anything.
There was a typo on the most recent exam that made True/False #7 false, but it was graded as if it were true. If you marked it false and lost two points, send me a screenshot of that in email/discord and I’ll give you your two points back.
For the Hamming code example we used in the notes, i.e. with generating matrix $\begin{pmatrix} 1& 0 & 0 &0&1&1&0 \\ 0&1&0&0&1&0&1 \\ 0&0&1&0&0&1&1 \\ 0&0&0&1&1&1&1 \end{pmatrix}$:
Write out the parity check matrix and check that the first row of the generating matrix is a codeword.
Suppose you receive the transmission 1000101. Determine the syndrome.
Determine the most likely codeword that was sent.
In class, I listed out 8 elements of the example cyclic code given, which lives in the ring $R = \mathbb{F}_2[x]/(x^7-1)$.
I wrote out all the 8 codewords we found in class, i.e. $g(x)x^k$ for various $k$. Find this list.
Verify that $g(x)(x^3 + x^2+1) = x^7-1 = 0$. Explain why this means that $g(x)f(x) = g(x)f_1(x)$ for some $f_1(x)$ of degree $2$ or lower.
How many elements of the ring $R$ of degree $\le 2$ are there?
Explain why the above means the elements we already found are all the elements of this code.
Please let me know your requests for review videos! Just let me know what review question or general topic (bite-sized please), and I’ll make and post a short explanatory video. This is to make up for the last lecture and office hours I’ll be missing while travelling.
We have a lot of administrivia with the end of semester approaching! Please read carefully through all this to maximize your grade!
This week is the last week for in-person make-ups. Reminder: you can make up at most one problem per test for Tests 1-3. If you scored 6 or less on your chosen problem, use my appointments calendar link (on canvas or discord) to make a 15 minute appointment for the problem. If you scored 7 or higher, you can do a written make-up due last day of class; you can see the makeup problems and dropbox in canvas. [editor’s note: canvas setup still in progress]
I’ve made a poster page to show off all the beautiful posters you made! Check it out here. You should consider presenting these at Math For All in April!
On the discord I posted a link to the poster presentation order for Fri Dec 6 / Monday 9th. Please be on time, since I’m going to have a timer set up to manage the slots and we are sticking to the schedule!
On Wednesday, Dec 11th, class will be a pre-recorded lecture which you can view at your leisure (I’m travelling).
Please review your self-eval sheets for daily posts and make sure they are nearly ready for final submit on the last day of class (on canvas upload).
Please be aware the final exam is cumulative, and includes coding theory.
FCQs are open! These matter! Please fill it out with your honest opinions and suggestions, as I try to improve the course each year. Here’s the link.
I won’t be able to have in-person review session for final (because of my travel) but I will try to make up for it by responding to discord requests with short video explanations of problems.
For those doing extra time, make sure you have arranged your final exam with me.
If needed, you’ll want to review the following aspects of linear algebra for studying linear codes:
vectors and matrix multiplication
vector space and subspace
span
basis (independence, uniqueness of expression in terms of a basis)
dimension
kernel of a linear transformation
row-space and column-space
rank-nullity theorem
transpose of a matrix
Consider the binary code C = {(0,0,1),(1,1,1),(1,0,0),(0,1,0)}. The alphabet is {0,1}.
What is the length of C?
What is d(C) (the minimum distance)?
What are q, n, M and d if C is a q-ary (n,M,d)-code?
How many errors can C detect?
How many errors can C correct?
Show that C is not linear.
Suppose you send the codeword (1,1,1) and 2 errors are made on the noisy channel, in the first and last positions. Explain what message is received and what it decodes to via nearest neighbour decoding. Was communication successful?
Show that C is a coset of a linear code. (The definition of a coset is a translation, by some vector, of a subspace). What is the linear code? Call it C’.
Find all the lines in $\mathbb{F}_3^2$ (think back to Monday’s class and tic tac toe); draw them all and give them their equations as names.
If a line goes through the origin, it is a subspace of dimension 1. Mark all the ones that are subspaces.
If a line doesn’t go through the origin, it is a translation of a line that does. For example, $y = x+2$ is a translation of $y=x$. Translation means sliding it around without changing its slope, or, equivalently, adding a constant to one side of the equation. For each subspace you marked, find out which lines are the translations of that subspace. The set of translations of a line are called its cosets.
Show that a line and a non-trivial translation of that line don’t intersect.
Suppose I send a message, which is an element of $\mathbb{F}_3^2$, i.e. a vector with two entries modulo $3$. Suppose the message is subject to a possible error (at most one) while in transit. Errors can happen in the following way: one of the two entries can accidentally be increased or decreased by one. If I sent $(1,2)$, what are the possible things that could be received? (E.g., $(1,1)$ is possible… there are five possibilities total, including no error.)
Now, continuing the situation above, which system (“code”) should I use to send a bit? I give two possibilities below. Which is the best system and why?
zero = (0,0), one = (0,1)
zero = (0,0), one = (1,1)
Can you come up with a better system to send a bit? What would better mean? (This is open ended.)
Let me know if there’s any problem scheduling the groups to present on Dec 6th and Dec 9th. If you need to be on one day instead of the other, let me know. Presentations will be 5 mins each with a very brief window for questions. I think we actually need to fit 8 talks in 50 minutes, so 5 mins present + 1 minute questions + 15 second changeover. I’ll bring a buzzer! You can arrange your presentation however you like, but I’ll put all the posters in a slide deck ahead of time.
I plan to put the posters up on a website (like the examples on the “Posters” tab, from other classes). Please let me know if you have any problem with your poster being publicly accessible. I think it would be great to make these available for future students! But it’s up to you.
Review Session Tuesday Nov 19th, 1:45-3 pm, starting in Math 350 and moving to Math 220 around 2:20 pm.
Test on Wednesday! I am working on putting up syllabus/review info in the usual place (Tests tab).
The Archive tab has the lecture notes, and the Overleaf text has a typeset version of Regev encryption (abstract & example).
Regev Encryption Ciphertext Chain!
Check out the Matrices Sage tools (a matrix calculator basically).
Decide on your favourite bit (either 0 or 1). You can interpret that in any way you want.
We will use $p = 3203$. Also $k = 13$, and $n=7$. (Note that in the Matrices tool above, there’s a hint about how to format matrices and vectors so they can be shared easily by cut and paste in discord. Send vectors as row vectors, so the entries are separated by commas, and people can transpose() them as needed.)
Play Bob: Set up a private/public key pair like Bob’s, and put the public portion as your public key on the #public-keys channel.
Play Alice: Find someone else’s public key and send them your message on the #ciphertexts channel.
Play Bob: Receive a message and decrypt it, posting it to the public channel in “spoiler” mode @mentioning the sender.
Play Alice: When someone reveals their decryption, please check it (it’s just a single bit, so this step is important so they know if it worked!) and let them know if it worked!
I will be giving feedback via canvas on the poster drafts. Keep working! It sounded like people wanted to have a “poster day” or two when we present them all, instead of a few at the beginning of each class. I’ll ask about that on discord to see.
It was pointed out to me that I have a unwitting habit of saying “first qubit” and “second qubit” when I mean “first register” and “second register” while discussing Shor’s algorithm. I apologize for this! I should never need to talk about the first and second qubits, so pretty much every time I’ve said the former, I meant the latter.
If you are interested in where continued fractions come from and why they are *SO* completely awesome, watch this video. It was one of the winners of #SoME3.
Compute the continued fraction expansion of 9/103 and the associated approximations.
Suppose you wish to factor N=35, using alpha = 9. Suppose you use 10 qubits in the first register and 6 qubits in the second register. Suppose Shor’s algorithm measures y=853 at the end (the final step measuring the first register). Explain how to finish off Shor’s algorithm to factor N.
If anyone got only one of the two square roots on the exam, problem 1.2 part 2 (square roots of 3 mod 11), you should get one point out of two. If you got zero points, send me a screenshot via DM on discord or via email and I’ll give you your point.
This series of problems asks you to work through Shor’s period-finding algorithm with two 3-qubit registers by hand. We begin with $|000\rangle |000\rangle$, and then we apply a QFT on the first register to get a uniform superposition. Demonstrate this (you have the 8×8 QFT from last daily post, solution is on #daily-collaboration on discord or in overleaf text). What is the output (as a combined state of both registers)? (Note: I said QFT inverse in class, but plain QFT does it too, so I didn’t need to say that.)
The next step in Shor’s algorithm is to apply $U_f$ for a periodic function $f$. Suppose we get the quantum state $\frac{1}{2\sqrt{2}}\left(|000\rangle |001\rangle + |001\rangle |010\rangle +|010\rangle |100\rangle +|011\rangle |011\rangle +|100\rangle |001\rangle +|101\rangle |010\rangle +|110\rangle |100\rangle +|111\rangle |011\rangle \right)$. This is the quantum state obtained in Shor’s algorithm immediately after applying the gate $U_f$ evaluating a function $f(x) = a^x \pmod{N}$ for some $a$ and $N$. Can you identify $a$ and $N$? (it’s ok if $N$ is prime or composite for this baby example)
Now, measure the second register in the state above. What are the possible output states (of the combined two registers) and probabilities?
Choose one of the four possible outputs from the last part. Apply the QFT on the first register (you have the QFT from the last daily post, and you have to do a matrix multiplication). What is the resulting state (of the combined two registers)?
Now measure the first register. What are the outputs and probabilities?