Reminder: The final exam is Friday, December 11th, 1:30–4 pm.

TBA

Reminder: The final exam is Friday, December 11th, 1:30–4 pm.

TBA

TBA

TBA

TBA

Reminder: Test 4 (Module 4) is in class on Wednesday, November 18th.

Test make-ups: you can still improve your Test 1 and Test 2 scores by retaking one Part B problem from each test (a written replacement problem on Canvas if you scored 7 or higher on it, or a 15-minute in-person retake booked through the calendar link on the Canvas main page if you scored 6 or lower). Details in the October 16th post.

TBA

Reminder: Test 4 (Module 4) is in class on Wednesday, November 18th.

Test make-ups: you can still improve your Test 1 and Test 2 scores by retaking one Part B problem from each test (a written replacement problem on Canvas if you scored 7 or higher on it, or a 15-minute in-person retake booked through the calendar link on the Canvas main page if you scored 6 or lower). Details in the October 16th post.

TBA

Poster reminder: the final version and report of work are due Friday, November 13th. Details on the Posters tab.

Test make-ups: you can still improve your Test 1 and Test 2 scores by retaking one Part B problem from each test (a written replacement problem on Canvas if you scored 7 or higher on it, or a 15-minute in-person retake booked through the calendar link on the Canvas main page if you scored 6 or lower). Details in the October 16th post.

TBA

Poster reminder: the final version and report of work are due Friday, November 13th. Details on the Posters tab.

Test make-ups: you can still improve your Test 1 and Test 2 scores by retaking one Part B problem from each test (a written replacement problem on Canvas if you scored 7 or higher on it, or a 15-minute in-person retake booked through the calendar link on the Canvas main page if you scored 6 or lower). Details in the October 16th post.

TBA

Poster reminder: the final version and report of work are due Friday, November 13th. Details on the Posters tab.

Test make-ups: you can still improve your Test 1 and Test 2 scores by retaking one Part B problem from each test (a written replacement problem on Canvas if you scored 7 or higher on it, or a 15-minute in-person retake booked through the calendar link on the Canvas main page if you scored 6 or lower). Details in the October 16th post.

TBA

Poster reminders: the first draft (complete, in LaTeX) is due Friday, November 6th, and the final version and report of work are due Friday, November 13th. Details on the Posters tab.

Test make-ups: you can still improve your Test 1 and Test 2 scores by retaking one Part B problem from each test (a written replacement problem on Canvas if you scored 7 or higher on it, or a 15-minute in-person retake booked through the calendar link on the Canvas main page if you scored 6 or lower). Details in the October 16th post.

Today we met the quantum Fourier transform (QFT). Since your poster drafts are due Friday, I’ll keep this daily post short, but it would be good to do a bit of basic computation with the QFT.

Relevant Textbook Sections:

Chapter 6 (Quantum): roots of unity and the quantum Fourier transform.

To Do:

1. Apply the $4 \times 4$ QFT matrix to the state

   $$\frac{1}{\sqrt{2}} \left( |00\rangle + \frac{1+i}{2} |01\rangle + \frac{1-i}{2} |11\rangle \right).$$

2. Draw the $8$th roots of unity in the complex plane and label them. You can use the $8$th root of unity notation $\omega := \omega_8 = e^{i\pi/4}$, but simplify so that the labels are from the set $\{1, -1, i, -i, \omega, -\omega, i\omega, -i\omega\}$.

3. Write down the QFT matrix of dimension $8 \times 8$. Again, use the notation $\omega := \omega_8 = e^{i\pi/4}$, but simplify so that the entries are all from the set $\{1, -1, i, -i, \omega, -\omega, i\omega, -i\omega\}$. (Hang on to this; we’ll use it to run Shor’s algorithm by hand next time.)

Optional: the Visualizing Complex Numbers & QFT and QFT Amplitudes pages (under the Tools menu, Module 4) let you watch the roots of unity sum up in the QFT of a periodic state.

Poster reminders: the first draft (complete, in LaTeX) is due Friday, November 6th, and the final version and report of work are due Friday, November 13th. Details on the Posters tab.

Solutions: solutions to the daily posts due October 23rd (qubits and the $L$/$V$ bases), October 26th (BB84 on paper, key length, catching Eve), October 30th (two-qubit states and entanglement), and November 2nd (multi-qubit measurement and single-qubit gates) are posted. All daily post solutions are collected on the Archive page.

Today we built gates on two and more qubits (CNOT, Hadamard on one qubit of a system, the reversible AND), and saw the general principle that any classical function can be computed quantumly, as long as we make it reversible. Here are some problems in those directions.

Relevant Textbook Sections:

Chapter 6 (Quantum): multi-qubit gates, CNOT, the reversible AND (Toffoli) gate, and computing classical functions reversibly.

To Do:

Unitary matrices.

1. Verify that the product of two unitary matrices is unitary. (This may require reviewing the transpose of a product.)
2. Verify that a unitary matrix is invertible and its inverse is unitary.

Two-qubit gates.

3. Verify that the CNOT gate $\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$ is unitary.
4. Apply the CNOT gate to the state $\frac{1+2i}{\sqrt{6}}|01\rangle + \frac{1}{\sqrt{6}}|10\rangle$.
5. Consider “applying the Hadamard gate to the second qubit” as a two-qubit gate.
   1. What does this do to the state $|00\rangle$?
   2. What does this do to the state $|01\rangle$?
   3. Write out the two-qubit $4 \times 4$ matrix that does this, and verify that it is unitary.
6. Begin with the 2-qubit state $|00\rangle$.
   1. Apply the CNOT gate to the 2-qubit system and then the Hadamard gate to the 2nd qubit.
   2. Start over with $|00\rangle$. Now apply the Hadamard gate to the 2nd qubit and then the CNOT gate to the system. Do you get the same answer?
   3. Repeat the last two parts with the Hadamard gate applied to the 1st qubit instead of the 2nd. Do you get the same answer this time? Is either output entangled?
7. Determine a $2$-qubit quantum circuit that will, on input $|00\rangle$, produce output $\frac{1}{2}|00\rangle + \frac{1}{2}|01\rangle + \frac{1}{2}|10\rangle + \frac{1}{2}|11\rangle$. Hint: combine Hadamard gates.

Classical functions, quantumly.

8. Apply the reversible AND gate (as demonstrated in class) to the state $\frac{1}{2}|000\rangle + \frac{1}{2}|011\rangle + \frac{1}{2}|101\rangle + \frac{1}{2}|111\rangle$.
9. Make an $8 \times 8$ unitary matrix that implements a reversible OR gate.
10. Let $f(x_1, x_2) = x_1 \oplus x_2$ (XOR), and let $U_f$ be the three-qubit gate $U_f |x_1 x_2\rangle |y\rangle = |x_1 x_2\rangle |y \oplus f(x_1,x_2)\rangle$.
    1. Describe what $U_f$ does to each of the eight basis states. Explain why this guarantees $U_f$ is unitary.
    2. Apply $U_f$ to $\frac{1}{2}\left( |00\rangle + |01\rangle + |10\rangle + |11\rangle \right)|0\rangle$. Notice that you have evaluated $f$ on all four inputs at once.
    3. Express $U_f$ as a composition of two CNOT gates.

Happy Almost Hallowe’en! Today we did two-qubit (and more-qubit) systems and met our first quantum gate, so here are a few problems in those directions.

Posters: don’t forget to work on your posters; check the Posters tab for the next deadline.

Relevant Textbook Sections:

Chapter 6 (Quantum): multiple qubits, entanglement, measuring one qubit of a multi-qubit state, and single-qubit gates.

To Do:

1. Consider the state $\frac{1}{\sqrt{2}}|01\rangle + \frac{1}{\sqrt{2}}|10\rangle$.
   1. What is the probability of measuring a $0$ in the first bit?
   2. What is the probability of measuring a $0$ in the second bit?
   3. What is the probability of measuring a $0$ in both bits? (I.e. after measuring both bits, what’s the probability you obtained $00$?)
2. For each of the following, determine if it is entangled or not (i.e. whether it can be written as a product of single-qubit states):
   1. $|111\rangle$
   2. $\frac{1}{\sqrt{2}}|10\rangle + \frac{1}{\sqrt{2}}|11\rangle$
   3. $\frac{1}{\sqrt{2}}|110\rangle + \frac{1}{\sqrt{2}}|111\rangle$
   4. $\frac{1}{\sqrt{2}}|010\rangle + \frac{1}{\sqrt{2}}|111\rangle$
3. In the state $\frac{1}{\sqrt{2}}|010\rangle + \frac{1}{\sqrt{2}}|111\rangle$, what is the probability of measuring a $0$ in the first qubit? middle qubit? last qubit?
4. Measure the following states in the first qubit and report the possible outcome bits, outcome states (the state of the system after the measurement), and probabilities. Don’t forget to normalize.
   1. the Bell state $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$
   2. $\frac{1}{\sqrt{14}}|01\rangle + \frac{2i}{\sqrt{14}}|10\rangle + \frac{3}{\sqrt{14}}|11\rangle$

Quantum gates. A bit of practice with the linear algebra behind gates:

5. Compute the complex conjugates of $3+7i$, $8$ and $8i$.
6. Compute the conjugate transpose of the complex matrix $\begin{pmatrix} 1 & 2+i \\ 3i & i \end{pmatrix}$. Check if this matrix is unitary.
7. Apply the Pauli $Z$ gate $\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$ to the single-qubit state $\frac{1+2i}{\sqrt{6}}|0\rangle + \frac{1}{\sqrt{6}}|1\rangle$. What is the output? Does measuring the output in the $|0\rangle$, $|1\rangle$ basis give different probabilities than measuring the input?
8. Consider the single-qubit states $|\psi\rangle = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$ and $|\phi\rangle = \frac{1}{\sqrt{2}}|0\rangle - \frac{1}{\sqrt{2}}|1\rangle$.
   1. Explain why, measuring the states in the basis $|0\rangle$, $|1\rangle$, you can’t tell the difference between these states.
   2. Now apply the Hadamard gate $H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ to both states. Explain what happens to $H|\psi\rangle$ and $H|\phi\rangle$ if you measure in the basis $|0\rangle$, $|1\rangle$. Can you tell the difference between these by measuring?
9. Create a unitary single-qubit gate that takes $|0\rangle$ to a normalized version of $|0\rangle + i|1\rangle$.

Today was Test 3. Take a breath! On Friday we continue Module 4 (Quantum) by moving from one qubit to two qubits, which is where quantum computing begins. The problems below are a warm-up for that: nothing here needs anything beyond the single-qubit rules from lecture (a state $a|0\rangle + b|1\rangle$ with $|a|^2 + |b|^2 = 1$ gives outcome $0$ with probability $|a|^2$ and outcome $1$ with probability $|b|^2$), but by the end you will have met the main new phenomenon with your own hands.

Relevant Textbook Sections:

Chapter 6 (Quantum): review single qubit states and measurement. On Friday we move on to multiple qubits.

To Do:

1. Two qubits, measured separately. Alice prepares two qubits, one after the other, and Bob measures each one in the $|0\rangle$, $|1\rangle$ basis.

   1. The first qubit is $|0\rangle$ and the second is $\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$. List the four possible pairs of outcomes (first qubit, second qubit) and the probability of each.
   2. Now both qubits are $\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$. List the four possible pairs of outcomes and their probabilities.
   3. Now the first qubit is $\frac{1}{\sqrt{5}}|0\rangle + \frac{2}{\sqrt{5}}|1\rangle$ and the second is $\frac{1}{\sqrt{2}}|0\rangle - \frac{1}{\sqrt{2}}|1\rangle$. Same question.

2. Two qubits as one state. We can write a pair of qubits as a single “two-qubit state” by writing the two states side by side. For the pair in problem 1(1), that is $|0\rangle\left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right)$. Multiply out as if these were ordinary products, keeping the first qubit first, and write $|0\rangle|0\rangle$ as $|00\rangle$, $|0\rangle|1\rangle$ as $|01\rangle$, and so on:

   $$|0\rangle\left(\tfrac{1}{\sqrt{2}}|0\rangle + \tfrac{1}{\sqrt{2}}|1\rangle\right) = \tfrac{1}{\sqrt{2}}|00\rangle + \tfrac{1}{\sqrt{2}}|01\rangle.$$

   The four states $|00\rangle$, $|01\rangle$, $|10\rangle$, $|11\rangle$ are the possible outcomes when both qubits are measured, and the squared lengths of the coefficients are the probabilities, just as for one qubit.

   1. Check that this agrees with your answer to 1(1).
   2. Multiply out $\left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right)\left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right)$ and check that it agrees with your answer to 1(2).
   3. Multiply out $\left(\frac{1}{\sqrt{5}}|0\rangle + \frac{2}{\sqrt{5}}|1\rangle\right)\left(\frac{1}{\sqrt{2}}|0\rangle - \frac{1}{\sqrt{2}}|1\rangle\right)$ and check that it agrees with your answer to 1(3). Note the minus signs: they don’t affect the probabilities here, but hang on to them.
   4. Check that in each case the squared lengths of the four coefficients add up to $1$.

3. An unusual two-qubit state. Now take the rule from problem 2 as the definition: a two-qubit state is any

   $$a|00\rangle + b|01\rangle + c|10\rangle + d|11\rangle, \qquad |a|^2 + |b|^2 + |c|^2 + |d|^2 = 1,$$

   and measuring both qubits gives outcome $00$ with probability $|a|^2$, outcome $01$ with probability $|b|^2$, and so on. Consider the state

   $$|\Phi\rangle = \tfrac{1}{\sqrt{2}}|00\rangle + \tfrac{1}{\sqrt{2}}|11\rangle.$$
   1. What are the probabilities of the four outcomes $00$, $01$, $10$, $11$ when Bob measures both qubits?
   2. What is the probability that the first qubit comes out $0$? (Add up the probabilities of all outcomes whose first bit is $0$.)
   3. Suppose Bob measures only the first qubit and gets $0$. What can he now say about the second qubit, before measuring it? Compare with the state from problem 2(2), where knowing the first outcome tells you nothing about the second.
   4. Try to write $|\Phi\rangle$ as a product of two single-qubit states, $(x|0\rangle + y|1\rangle)(z|0\rangle + w|1\rangle)$, by multiplying out and comparing coefficients. Show that it is impossible. (You will need $xw = 0$ and $yz = 0$, but also $xz \neq 0$ and $yw \neq 0$.)

   A state that cannot be written as a product of single-qubit states is called entangled. Its two qubits are not independent, even if they are far apart.

4. Normalize first. Normalize the state $|00\rangle + 2i|01\rangle - 2|11\rangle$, then give the probabilities of the four outcomes when both qubits are measured. Is it a product state or entangled?

Reminder: Test 3 (Module 3) is in class on Wednesday, October 28th. The syllabus and review problems are on the Tests tab.

Today’s slides, Here comes the Hackpocalypse (cybersecurity in the AI era), are posted; they are also linked from the Notes/Videos page and the Archive.

To Do:

1. Study for the test on Wednesday!

Reminder: Test 3 (Module 3) is in class on Wednesday, October 28th. The syllabus on the Tests tab is now updated (elliptic curves, plus the quantum material through today: qubits, superposition, measurement, and quantum key distribution), along with review problems.

Today we finished Quantum Key Distribution (BB84)!

Lecture notes and video: my notes from today’s Zoom lecture are posted (also on the Notes/Videos page and the Archive). The link to the Zoom recording is on discord.

Relevant Textbook Sections:

Chapter 6 (Quantum): quantum key distribution.

To Do:

We use the encoding from lecture: in the $L$ basis, $|\uparrow\rangle$ is the bit $0$ and $|\rightarrow\rangle$ is the bit $1$; in the $V$ basis, $|\nwarrow\rangle$ is the bit $0$ and $|\nearrow\rangle$ is the bit $1$.

1. Play Alice and Bob on paper. Alice sends eight photons and Bob measures them:

   Photon	1	2	3	4	5	6	7	8
   Alice’s basis	$L$	$V$	$V$	$L$	$V$	$L$	$L$	$V$
   Alice’s bit	1	0	1	1	0	0	1	0
   Bob’s basis	$L$	$L$	$V$	$V$	$V$	$L$	$V$	$V$
   Bob’s measured bit	1	1	1	0	0	0	1	0

   1. Which photon (which arrow) did Alice send each time?
   2. After Alice and Bob announce their bases publicly, which photons do they keep? What is their shared secret key?
   3. For photon 2, Bob measured a $1$ but Alice sent a $0$. Explain why this is not an error, and why photon 2 tells Bob nothing about Alice’s bit.
   4. Eve was listening to the public conversation. What does she learn?

2. Quantum Key Distribution in pairs! I think this will get confusing with everyone simultaneously on the #ciphertexts channel, so I want you to do this in pairs in the “QKD pairs” channel category of discord. There you will find plenty of text channels, so fill them up with two people each as you arrive, taking the first empty spot (the first person needing a partner or the first unused channel). Announce your arrival. The first person to arrive in a channel is Alice, the second person to arrive is Bob. Once two people are there, it’s full, so pick the next channel. You’ll do all communication on the channel so I can help you debug if it doesn’t work.

   • Open up the QKD BB84 Tools. The first box contains some code to initialize; no need to read this, just run it. The second box is a spot where you can either create photons (in our instantiation, they are just mysterious looking integers), or measure existing photons. It just holds an example for now.
   • Once you know if you are Alice or Bob, follow the protocol for your role.
   • If playing the role of ALICE:
     1. Here’s a spreadsheet you might find useful (optional; view only but you can copy it).
     2. Choose a sequence of 16 random choices of basis: example V L V V etc. The best way to do this is with a random number generator (like randint() in Sage).
     3. Now choose a sequence of 16 bits: example 011001010101 etc. Again, true or good pseudo-randomness is best.
     4. Use your two sequences to generate photons using the command generate_photon in the QKD BB84 Tools page. This will create 16 integers (the photons), which you should obtain and paste into the channel as your “outgoing photon stream”.
     5. Wait until Bob harvests your photon stream and reports that they are done “measuring” the photons.
     6. Then, post to the channel the list of bases you used on your photons.
     7. Bob will also post their list of bases used on the channel.
     8. Then, determine the shared secret key from these two lists. Share it and see if Bob agrees.
   • If playing the role of BOB:
     1. Here’s a spreadsheet you might find useful (optional; view only but you can copy it).
     2. Choose a sequence of 16 random choices of basis: example V L V V etc. The best way to do this is with a random number generator (like randint() in Sage). Keep this secret for now.
     3. Alice will create a stream of photons (integers). Harvest (cut-n-paste) Alice’s photon stream, and use the command measure_photon() in the QKD BB84 Tools page to measure them using your list of bases (first basis to measure first photon etc.) Record the measurements and keep them secret.
     4. Report to the channel you have finished measuring.
     5. Then, report to the channel your list of bases.
     6. When Alice also reports her list of bases, derive the shared secret.
     7. Then, post the shared secret you derived to check if it agrees with Alice’s.
   • To Do: When you’re done, just post to canvas a screenshot or record of your experience; you can screenshot the channel or you can screenshot your spreadsheet or a text file you kept a record in; whatever, just to show you did it.

3. How long is the key?

   1. For each photon, what is the probability that Alice and Bob chose the same basis?
   2. In the pairs exercise above, you sent 16 photons. What is the expected length of the shared key? What is the probability that the key has exactly that length? How long was the key you actually got?
   3. If Alice and Bob need a 128-bit key, about how many photons should Alice send?

4. Eve intercepts. Alice sends $|\nearrow\rangle$. Eve intercepts it, measures it in the $L$ basis, and sends Bob a fresh photon in whatever state she measured. Bob measures in the $V$ basis.

   1. What are the possible outcomes of Eve’s measurement, and their probabilities? What photon does she send on to Bob in each case?
   2. What is the probability that Bob measures the bit $1$, as Alice intended?
   3. What would have happened if Eve had guessed the $V$ basis instead?

5. Catching Eve. Now suppose Eve intercepts every photon, measures each in a randomly chosen basis, and resends what she measured.

   1. Consider a photon where Alice and Bob chose the same basis (so it goes into the key). Show that the probability Bob’s bit disagrees with Alice’s is $\frac{1}{4}$.
   2. To check for Eve, Alice and Bob publicly compare 20 of their key bits (and then throw those bits away). If Eve intercepted every photon, what is the probability that all 20 bits agree anyway, so Eve goes undetected?
   3. Why is it safe for Alice and Bob to announce their bases publicly, but not their bits?

Reminder: Class on Friday, October 23rd will again be on Zoom, due to my illness. The link is in Canvas. If you need a quiet place to join, you are welcome to use our usual classroom. The class will be recorded, but please attend synchronously if you can.

Welcome to Module 4: Quantum! Today we met complex numbers, qubits, measurement, the $L$ and $V$ bases, and the three filter experiment.

Lecture notes and video: my notes from today’s Zoom lecture are posted (also on the Notes/Videos page and the Archive). The link to the Zoom recording is on discord.

Relevant Textbook Sections:

The opening of Chapter 6 (Quantum): complex numbers, single qubit states, and measurement.

To Do:

1. Complex numbers worksheet. Work through whatever parts are most useful or interesting to you of the online Complex Numbers Worksheet. My suggestion: if you’re comfortable with complex numbers as done in class, then start at “Domain Colouring,” which is just lovely. If complex numbers are new to you, the earlier parts of the worksheet will give you the practice you need for the rest of the module.
2. Compute the length of the complex number $\frac{3}{5} + \frac{4}{5}i$. (The answer should be $1$; please make sure you got this!)
3. Consider the qubit superposition $i|0\rangle + \sqrt{3}|1\rangle$.
   1. Normalize it so that $|a|^2 + |b|^2 = 1$.
   2. Measure it in the basis $|0\rangle$, $|1\rangle$. What are the possible outcomes and their probabilities?
4. Recall the $L$ basis $|\uparrow\rangle$, $|\rightarrow\rangle$ and the $V$ basis $|\nearrow\rangle$, $|\nwarrow\rangle$, where $|\nearrow\rangle = \frac{1}{\sqrt{2}}\left(|\uparrow\rangle + |\rightarrow\rangle\right)$ and $|\nwarrow\rangle = \frac{1}{\sqrt{2}}\left(|\uparrow\rangle - |\rightarrow\rangle\right)$.
   1. Measure $|\nearrow\rangle$ in the $L$ basis (i.e. give the outcomes and their probabilities).
   2. Measure $|\nearrow\rangle + i|\nwarrow\rangle$ in the $L$ basis. (Normalize first!)
5. Consider the state $|\psi\rangle = \frac{1}{\sqrt{5}}|\uparrow\rangle + \frac{2}{\sqrt{5}}|\rightarrow\rangle$.
   1. Measure it in the $L$ basis. What are the possible outcomes and their probabilities?
   2. Measure it in the $V$ basis. What are the possible outcomes and their probabilities? (To do this, you will first need to write $|\psi\rangle$ as a normalized linear combination of $|\nearrow\rangle$ and $|\nwarrow\rangle$.)

Reminder: Class on Wednesday, October 21st is on Zoom. The link is in Canvas. If you need a quiet place to join, you are welcome to use our usual classroom. The class will be recorded, but please attend synchronously if you can.

Solutions: solutions to the daily posts due October 16th (elliptic curve multiples table) and October 19th (EC El Gamal chain and Pollard $p-1$) are posted. All daily post solutions are collected on the Archive page.

Relevant Textbook Sections:

5.4 (Factoring with elliptic curves), including 5.4.1 (An example motivating the key idea), 5.4.2 (Pollard’s $p-1$ factoring algorithm) and 5.4.3 (Elliptic Curve Factoring). Review 3.8.1 (Pollard’s rho factoring method).

To Do:

1. Finish up the Elliptic Curve El Gamal ciphertext chain from last time: make sure you have decrypted any message encrypted to your public key (and announced the plaintext, @mentioning the sender), that your own message has been decrypted and confirmed, and that your notes are handed in to the canvas dropbox.
2. On the curve $y^2 = x^3 + x + 1$ modulo $91$, check that $P = (0,1)$ and $Q = (7,13)$ are on the curve, and then try to compute $P + Q$ by hand. What goes wrong when you compute the slope? Use the failure to factor $91$. Then reduce $P$ and $Q$ modulo each prime factor of $91$: what is $P + Q$ modulo each prime? Explain why the computation broke down.
3. Use the EC Factoring Example page to factor $n = 290265623$. You might want to increase the size of the loop! Write up a short explanation of your work.
4. A factoring race. We now have three factoring methods that each look for a prime factor $p$ of $n$ “by accident.” Run all three on the same $n = 290265623$ from problem 3 and record how long each one takes:
   1. Pollard’s $\rho$ with $f(x) = x^2 + 1$ and $x_0 = 2$: how many steps until $\gcd(x_{2i} - x_i, n)$ is nontrivial? ($n$ is too big for the Pollard Rho Demo, so use the Sage Pollard Rho page, which keeps a tortoise and a rabbit and prints the gcd at each step.)
   2. Pollard’s $p-1$ with $a = 2$ (use the Pollard p-1 page from last time): what is the first $B$ for which $\gcd(a^{B!}-1, n)$ is nontrivial? Again, you may need to increase the size of the loop.
   3. Elliptic curve factoring (problem 3; you already did this): which multiple blew up?
5. Now factor $p - 1$ for each prime factor $p$ of $n$ from the last problem. Use this to explain the $p-1$ result exactly.
6. Recall that Pollard’s $\rho$ takes about $\sqrt{p}$ steps. Compare $\sqrt{p}$ with your step count from problem 4.
7. In Sage, EllipticCurve(GF(p), [1,1])(0,1).order() computes the order of the point $(0,1)$ on $y^2 = x^3 + x + 1$ modulo a prime $p$ (change the coefficients and the point if you used a different curve in problem 3). Compute this order modulo each prime factor of $n$, and factor the answers. Use this to explain which multiple blew up in problem 3.
8. For which kinds of $n$ would you choose $\rho$, which $p-1$, and which elliptic curves?
9. If time remains, explore EC Factoring further:
   1. Factor $n = 290265623$ again with a different choice of curve and point (revisit lecture for some advice on finding random curve + point pairs).
   2. Try modifying one of the middle digits of $n$, and see how long it takes. Factor $n$ completely using Sage’s factor() function, to see what kinds of primes it has in it. Repeat a few more times.
   3. Report/discuss on discord on how long it took (i.e., what multiple of $P$ blew up) on different curves and points, and different $n$. Explain why you think it was fast sometimes and slow other times. You can use the #daily-collaboration channel.

Test make-ups: You have an opportunity to improve your grade on Test 1 and Test 2. Here’s how it works. For each test, you may retake one of the 10 point problems in Part B that you attempted. That means solving a similar problem. Your retake score replaces your original score on that problem, so you can completely make up the lost points (up to the full 10 points).

• If you got 7 or higher on your problem, you will do a written replacement problem. The written retakes are posted on canvas.
• If you got 6 or lower, you will schedule to meet in person for a retake. Use the calendar link on the canvas main page for appointments (15 minute slot).

Deadlines: Test 1 make-ups must be done by the end of October (Friday, October 30th). Test 2 make-up deadline: TBA.

Relevant Textbook Sections:

5.6 (Elliptic Curve Diffie-Hellman), 5.7 (Elliptic Curve El Gamal), including 5.7.1 (Placing a message on a curve) and 5.7.2 (Square roots modulo $p$).

To Do:

1. An Elliptic Curve El Gamal Ciphertext Chain! Today’s question: best hallowe’en costume? You will encrypt your answer. Here are the steps:
   1. Keep notes as you do all this. Here are the EC El Gamal Tools you can use to do this.
   2. As a group, we will all use the elliptic curve $E$ given by $y^2 = x^3 + x^2 + x + 1$ over the finite field of $p = 123456789101234567891027$ elements. We will furthermore use the point P = E([3,11655832467975276266127,1]) on $E$, which has order $61728394550949287614731$.
   3. You should create a private and public key pair based on the information given above. Publish your public key on the #public-keys channel on discord (note: this is a point $(x,y)$ on the curve). Keep your private key in a text document somewhere to use for decrypting later.
   4. You should answer the question (Best hallowe’en costume?) with a word of 6 or fewer letters. Translate this to an integer (Text to Integer tool as usual) and add three digits of “padding” “000” at the end.
   5. Turn your message into a point on the elliptic curve as described in class. This might mean updating the padding to “001”, “002” etc. until it works. For this step, you need to take modular square roots. The command is sqrt. For example, sqrt(Mod(2,7)) will give you the square root of $2$ modulo $7$ (which is $3$). If it returns something with the string ‘sqrt’ in it, that means it failed (no square root), e.g. sqrt(Mod(3,7)) will just return sqrt3 — that means no square root.
   6. You should then obtain the most recent public key on the #public-keys channel, and encrypt your message (turned into a point on the curve) to that public key. Post your encryption to the #ciphertexts channel, @mentioning the owner of the public key it is encrypted to.
   7. You should then keep an eye on the channel and when someone encrypts a message to your public key (they should @mention you), you should decrypt it and announce what the plaintext was, @mentioning them back.
   8. When someone decrypts your message, you should give them a thumbs up to let them know it’s right (or let them know if it isn’t).
   9. Hand in your notes from this exercise to the canvas dropbox.
   10. Challenge for fun: break someone else’s message! Hint: factor the order of $P$.
2. Today we introduced Pollard’s $p-1$ algorithm. As a recap, to factor $n$, we take some $a$ modulo $n$, and create a chain $a, a^2, a^{3!}, a^{4!}$, etc. At each point, we take $\gcd(a^{B!}-1,n)$, hoping to get a nontrivial factor. We didn’t explain why it works. Can you reason out why it might work, at least heuristically?
3. Write a small Sage for loop (use the Sage Sandbox) to implement Pollard $p-1$ factoring. Use it to factor $n=16637$. Some hints so you don’t get stuck:
   1. remember to make $a$ into a value modulo $n$, for example with a = Mod(2,n) (it will actually work with integers but they grow so fast it isn’t efficient).
   2. when you want to take a gcd of a value mod $n$, you need to make it an integer again by putting a ZZ around it, so like gcd(ZZ(a)-1,n).
   3. start your loop at power $2$ (squaring), not zero.
4. With perfect timing, this discovery about the history of the NIST elliptic curves was released today! https://www.anthropic.com/research/ecdsa-curve-origins

Solutions: solutions to the daily post due October 14th (projective space) are posted. All daily post solutions are collected on the Archive page.

Test 2 solutions: Test 2 (Module 2) with solutions are posted (also linked from the Tests tab).

Tools: if you want more practice adding points by hand, the Practice Problems page makes random elliptic curve addition problems, and the Elliptic Curve Tools page and the Elliptic Curve Playground will check your work.

Relevant Textbook Sections:

5.5 (Elliptic Curve Discrete Logarithm Problem).

To Do:

On the elliptic curve $E: y^2 = x^3 + x + 1$ modulo $11$, take $P = (1,5)$. Its multiples are:

Every point of $E$ appears in this table. Use it for all the problems below.

1. How many points does $E$ have? Check that this satisfies Hasse’s bound.
2. If you have an elliptic curve modulo $13$, what is the maximum and minimum number of points it could have?
3. Using only the table (no slopes!), compute $(3,3) + (8,9)$ and $(6,5) + (6,5)$.
4. Using the table, find $-(4,6)$. Check that it agrees with what you know about negating a point geometrically.
5. What is the order of $7P = (2,0)$? Connect this to problem 5 from the daily post due October 12th. Which points of $E$ have order $7$? Which have order $14$?
6. (ECDLP) Find $k$ such that $kP = (6,6)$. The table makes this a lookup. Explain why, for a curve modulo a $256$-bit prime, nobody can write down this table, and why being able to compute any single $kP$ quickly (by double-and-add) doesn’t help you solve for $k$.
7. In the next class, we’ll define Elliptic Curve Diffie Hellman. But in class today, I already explained how the work we did in the first unit has an analogue for an elliptic curve. So you can already define this yourself! Write down what should be the Elliptic Curve Diffie Hellman protocol, and bring it to class to compare to what we do.

Posters: your group’s poster plan is due on canvas; check the Posters tab for the date and details, and make contact with your group and make a plan.

Lecture notes: my notes from today’s lecture on projective space are posted (also on the Notes/Videos page and the Archive).

Solutions: solutions to the daily post due October 12th (elliptic curve addition) are posted. All daily post solutions are collected on the Archive page.

Relevant Textbook Sections:

5.3 (Projective space).

To Do:

1. Make sure you did last day’s daily post and compare to the solutions. Those computations are important; we’ll use them more. Notice in particular what to do if your slope has a denominator, or you are adding a point to itself.
2. Give an example of four different vectors in $\mathbb{R}^2$ which become the same in $\mathbb{P}^1_\mathbb{R}$.
3. In the textbook (Section 5.3) and in lecture, we studied $\mathbb{P}_{\mathbb{F}_3}^2$: the $26$ nonzero vectors in $\mathbb{F}_3^3$ fall into equivalence classes, each drawn in a different colour. Pick one colour, write out the vectors in that equivalence class, and check that they are equivalent. How many classes are there in total?
4. Reward yourself with this video.
5. Compute a full list of the elements in $\mathbb{P}_{\mathbb{F}_5}^1$. Each element is an equivalence class (a bunch of different vectors that differ by scalar multiplication), so write out all the vectors in each equivalence class. (We did this for $\mathbb{P}_{\mathbb{F}_3}^1$ in class.)
6. In general, in $\mathbb{P}_{\mathbb{F}_{p}}^k$, how many vectors are in each equivalence class? For example, in the example from lecture, in $\mathbb{P}_{\mathbb{F}_{3}}^1$, there were $2$ in each class. What is the size of $\mathbb{P}_{\mathbb{F}_{p}}^k$ (i.e. how many equivalence classes)?
7. Find all the points of the affine equation $y^2 = xy - 1$ on the “line at $\infty$”. (Hint: we did this with the elliptic curve at the end of lecture: first homogenize the equation so all terms have the same degree, then break into $Z=0$ and $Z \neq 0$ cases.)
8. In lecture we saw that the elliptic curve $E: Y^2 Z = X^3 + aXZ^2 + bZ^3$ has exactly one point on the line at $\infty$, namely $[0,1,0] = \infty$. Check that the vertical line $x = c$ in the affine plane, written projectively as $X = cZ$, also passes through $[0,1,0]$. This is the precise sense in which “a vertical line meets $E$ at $\infty$,” which is what makes $P + (-P) = \infty$ in the group law from last week.

Posters: the poster plan (title, abstract, references, group expectations) is due soon. Check the Posters tab for the dates and for what goes in the plan. Not in a poster group yet? Please come talk to me (after class, office hours, or email) so we can sort that out before the plan is due.

Lecture notes: my notes from Friday’s lecture on elliptic curves and the group law are posted (also on the Notes/Videos page and the Archive).

Solutions: solutions to the daily posts due September 28th and 30th and October 2nd, 5th and 7th are now posted (Sep 28, Sep 30, Oct 2, Oct 5, Oct 7). All daily post solutions are collected on the Archive page.

Tools: the Elliptic Curve Tools page (Sage) will add points for you, and the Elliptic Curve Playground draws the whole group as a picture. Do the problems below by hand first, then use these to check.

Relevant Textbook Sections:

5.1 (What is an elliptic curve?), 5.2 (Double points).

To Do:

1. Compute the sum of the following two points on this elliptic curve. $E: y^2 = x^3 + x + 1$ modulo $7$. $P = (0,1)$ and $Q = (2,2)$. Compute $P+Q$.
2. What is $P + \infty$ on this curve?
3. What is $-P$?
4. Suppose, on the same curve, we want to compute the sum of $Q$ with itself. That means we need to find a tangent line! Compute $Q+Q$.
5. Show that if $P=(x,0)$ is a point on an elliptic curve, then $2P = \infty$.
6. On the curve $y^2 = x^3 +2x + 1$ modulo $5$, compute the sum of the two points $P = (3,3)$ and $Q = (1,2)$ by hand. Check that your answer is on the curve.
7. On the curve $y^2 = x^3 +2x + 1$ modulo $7$, try to compute the sum of the two points $P = (0,6)$ and $Q = (0,1)$ by hand. The result should be the point at infinity (because these are inverses of each other), so the computation will “fail” — explain what fails that lets you know the result is the point at infinity.
8. (A preview of things to come) On the curve $y^2 = x^3 +2x + 1$ modulo $35$, try to compute the sum of the two points $P = (28,13)$ and $Q = (21,22)$ by hand. The result will fail. Explain why it fails, and how the failure factors $35$. Explain the relationship to the previous two problems.

Reading day, take some recovery time! See you Friday. I’m postponing poster project dates and will post more about that on Friday.

Reminder: Test 2 (Module 2) is in class this Wednesday, October 7th (full period). The syllabus and review problems are on the Tests tab.

Test 1 solutions: Test 1 (Module 1) with solutions are posted (also linked from the Tests tab).

New tool: the Pollard Rho Demo page walks through Pollard’s $\rho$ method one step at a time: the tortoise-and-rabbit table from class, the $\rho$-shaped picture of the sequence, and (behind the scenes) what happens modulo each prime factor.

Relevant Textbook Sections:

3.8.1 (Pollard’s rho factoring method).

To Do:

1. Use Pollard’s rho method with $f(x) = x^2 + 1$ and $x_0 = 2$ to factor $n = 8051$. You may use the Pollard Rho page or the Sage Sandbox for the arithmetic. Afterwards, check your table against the Pollard Rho Demo (it has $8051$ as a preset), and look at its pictures modulo $83$ and $97$: why did the method find $97$ and not $83$? Then try $n = 10403$ and $n = 455459$ on that page.
2. Explain, using the birthday paradox, why Pollard’s rho typically finds a prime factor $p$ of $n$ after about $\sqrt{p}$ steps. (Hint: the sequence $x_i \bmod p$ behaves like random values modulo $p$, and you are waiting for a collision modulo $p$.) If $n$ is an RSA modulus with two $100$-digit prime factors, about how many steps is that?

Reminder: Test 2 (Module 2) is in class on Wednesday, October 7th.

Relevant Textbook Sections:

3.8.3 (The role of squares in factoring).

To Do:

1. Suppose $p \equiv 3 \pmod 4$ and $a$ is a square modulo $p$. The following observation gives a method to compute a square root of $a$. Explain why our setup implies $a^{(p-1)/2} \equiv 1$. Show that $x = a^{(p+1)/4}$ satisfies $x^2 \equiv a \pmod p$. Demonstrate the method with $p = 19$ and $a=6$. What goes wrong if you try the same formula for $p = 13$ and $a = 10$? (Note $6^2 \equiv 10 \pmod{13}$, so $10$ does have square roots.)
2. Suppose $n$ is a product of two primes which are $3 \mod 4$. Explain how, if you can factor $n$, you could find square roots modulo $n$ using the last exercise. (Hint: CRT.)
3. Find all four square roots of $71$ modulo $77 = 7 \cdot 11$. Hint: find the square roots modulo $7$ and modulo $11$ separately, then combine them with CRT.
4. Explain how, if you can find square roots modulo $n$, this allows you to factor $n$. (Find square roots means find all square roots.) Hint: this is just recalling something we’ve been discussing in class about square roots and factoring.
5. Just a note: There are also more complicated ways to find square roots modulo primes that are $1$ modulo $4$. So the exercises above show that factoring $n$ is considered equivalent to finding square roots modulo $n$.
6. Find the square root(s), if any, of $3$ modulo $11$ using the algorithm from the first example. Now draw the dynamical portrait of powers of $3$ modulo $11$. Label each vertex as $3^x = y$ for whatever $x$ and $y$, so each vertex can be interpreted as its value mod $p$ and its power of $3$. Can you use this diagram to explain why the method works?

New tool: the CRT Demo page shows the Chinese Remainder Theorem as two meshed gears (mod $m$ and mod $n$) turning a big mod $mn$ dial, along with the table from class. Try it with $m$ and $n$ coprime, and then with $m$ and $n$ sharing a factor.

Relevant Textbook Sections:

3.3 (Computing modular inverses), 3.4 (Sunzi’s Theorem (Chinese Remainder Theorem)).

To Do:

1. Find the inverse of $35$ modulo $61$. Use the extended Euclidean algorithm. Verify your answer by multiplying out.
2. Try out this Chinese Remainder Theorem problem, by hand: $x \equiv 3 \pmod{244}$ and $x \equiv 17 \pmod{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.
3. Use any remaining time to do extra examples of CRT problems (you can make up your own by just putting in whatever numbers you want, as long as the moduli are coprime, and you can always check your answer by plugging it back into the original equations). The CRT Demo page can solve small ones too (moduli up to 20), so you can check your answers there.
4. (AI suggestion) Sunzi’s original problem (c. 3rd–5th century): “There are certain things whose number is unknown. Counted by threes, two are left over; by fives, three are left over; by sevens, two are left over. How many things are there?” Solve it using CRT with three congruences.
5. (AI suggestion) When the moduli are not coprime, CRT can fail. Does $x \equiv 3 \pmod 6$, $x \equiv 5 \pmod 8$ have a solution? What about $x \equiv 1 \pmod 6$, $x \equiv 2 \pmod 8$? Explain when such a system has a solution, and how many solutions it has modulo $24$.
6. (AI suggestion) Another way to invert modulo a prime: by Fermat’s little theorem, $a^{-1} \equiv a^{p-2} \pmod p$. Compute $35^{59} \bmod 61$ and compare with problem 1. Which method would you rather use for a 300-digit prime, and why? Which method still works modulo a composite $n$?
7. (AI suggestion) CRT speeds up RSA. Alice’s key from the last daily post is $n = 3233 = 61 \cdot 53$, $e = 17$, $d = 2753$, and she receives the ciphertext $c = 2790$. Instead of computing $c^{d} \bmod 3233$ directly, compute $c^{d} \bmod 61$ and $c^{d} \bmod 53$ (why may you reduce the exponent $d$ modulo $60$ and modulo $52$ respectively?), and then combine the two answers with CRT. Check your answer against the direct computation. Why is this faster?
8. (AI suggestion) Håstad’s broadcast attack. Bob sends the same message $m$ to three friends, all using $e = 3$, with public moduli $n_1 = 55$, $n_2 = 391$, $n_3 = 1189$. Eve sees the ciphertexts $c_1 = 3$, $c_2 = 189$, $c_3 = 370$. Use CRT to find $X$ modulo $n_1 n_2 n_3$ with $X \equiv c_i \pmod{n_i}$ for each $i$. Explain why $X$ must equal $m^3$ exactly (as an integer, not just modulo something), and recover $m$. What does this suggest about sending the same message to several people with a small $e$?

Relevant Textbook Sections:

3.1 (The Euclidean Algorithm), 3.2 (The Extended Euclidean Algorithm).

To Do:

1. If you’d like a refresher on today’s material, watch my videos on the Euclidean algorithm and the Extended Euclidean algorithm (also on the Notes/Videos page). You can also play with the new Euclidean Algorithm page, which shows the algorithm as piles of dots and walks you through the recipe cards; use it to check your answers below.
2. Compute the gcd of 135 and 170. Show all the steps of the algorithm.
3. Consider the equation $7x + 15y = 1$. Find an integer solution to this equation using inspection or trial and error. Using it, tell me the inverse of $7$ modulo $15$ and the inverse of $15$ modulo $7$. (This should require no computation, just look at your solution and have an aha moment!)
4. Compute the gcd of 183 and 105. Show all the steps of the algorithm. Verify using the Sage Sandbox.
5. Solve $183x + 105y = 3$ by expanding your work above into “recipe cards” as shown in class. Verify your answer using Sage’s command xgcd in the Sage Sandbox.
6. What if we want to solve $3x + 5y = 0$? The zero is the weird part. Then we don’t use the Euclidean algorithm.
   1. Give one solution by inspection (just find a clever one).
   2. Now give another one different from the first.
   3. Now give infinitely many.
   4. Find a solution to $3x + 5y = 1$ (using the algorithm from class, or by guessing one).
   5. Now find infinitely many different solutions to $3x + 5y = 1$. (Hint: use parts 1–4.)
7. The goal of this exercise is to work out the runtime of the Euclidean algorithm (you may have seen this already, but do this without looking anything up). Think of the Euclidean algorithm as replacing one pair $(a,b)$ with a new pair $(a',b') = (b, a - qb)$ at each step. For example, if we start with $(a,b) = (183,105)$, then we get $(a',b') = (105,78)$ at the next step.
   1. Show that, if $b < a/2$, then $b' < a/2$.
   2. Show that, if $b \ge a/2$, then $b' \le a/2$.
   3. Conclude that after two steps $(a,b) \rightarrow (a',b') \rightarrow (a'',b'')$, the size of the first entry has decreased by at least half.
   4. What is the runtime of the Euclidean algorithm?
8. (AI suggestion) Run the Euclidean algorithm on $89$ and $55$ and count the steps. Now try some other pairs of numbers of about the same size. Why are consecutive Fibonacci numbers such slow inputs? How does this compare with your bound in the previous problem?
9. (AI suggestion) Which integers $c$ can be written as $12x + 42y$ for integers $x, y$? Explain. Then find all integer solutions of $1071x + 462y = 21$.
10. (AI suggestion) Use Sage to compute $\gcd(2^{12} - 1, 2^{18} - 1)$, and a few more like it, such as $\gcd(2^{a} - 1, 2^{b} - 1)$ for other $a, b$. Guess a formula. Can you explain it by running the Euclidean algorithm “in the exponents”? (Hint: $2^{a} - 1 = 2^{a-b}(2^{b} - 1) + (2^{a-b} - 1)$.)

Friday’s lecture (September 25th) is pre-recorded. Watch it before Monday:

• Video: Friday, September 25th lecture
• Notes: part 1 (the quadratic sieve, visually) and part 2 (signatures, RSA signatures, and cryptographic hash functions)
• These are also on the Notes/Videos page and the Archive.

Solutions: solutions to the daily posts due September 14th and 25th are now posted (Sep 14, Sep 25). All daily post solutions are collected on the Archive page.

Relevant Textbook Sections:

2.11 (Signature Schemes), 3.6.5 (RSA Signature).

To Do:

1. Watch the Friday, September 25th lecture (notes: part 1, part 2).
2. Fix integers $a$ and $b$ with $\gcd(a,b) = 1$, and suppose you have found integers $x, y$ with $ax + by = 1$ (for example, using the extended Euclidean algorithm). Explain why this single equation gives you both the inverse of $a$ modulo $b$ and the inverse of $b$ modulo $a$ at the same time. (Hint: reduce the equation modulo $b$, and then modulo $a$.)
3. Alice’s RSA key has $n = 3233 = 61 \cdot 53$ and $e = 17$. Find her private exponent $d$, sign the message $m = 65$, and then verify the signature as Bob. (The RSA Tools and other Sage functions may help.)
4. Using only Alice’s public key, pick any $s$ you like (say $s = 100$) and produce a message $m$ for which $s$ verifies as “valid”. Why doesn’t this worry Alice much in practice?
5. Alice has signed $m_1 = 65$ (signature $s_1 = 588$) and $m_2 = 42$ (signature $s_2 = 3065$). Without knowing $d$, produce a valid signature on $m_1 m_2 \bmod n$. Can you think of a way this could be exploited by an attacker? How would signing $h(m)$ instead of $m$ stop this attack?
6. Visit the Hash Tools page and make sure you understand what a hash function is and how to use the tools on this page.
7. Using the Hash Tools page, perform the SHA-256 hash on the string “friend” (try showing the digest both as hex and as bits). Then tick “Compare with a second message” and show the result in bits, change it to “fiend” (remove the r), and compare. Try some other pairs: united/untied, awesome/yuck, loooooooooong/short etc. How many of the 256 bits change? Is that what you’d expect?
8. For the checksum “hash” $h(m) = \sum \text{bits of } m \pmod 2$ from lecture, find a preimage of $0$, and find a collision with $m = 1010$.
9. How about another toy hash which XORs together all the 8-bit blocks of $m$ to produce a single 8-bit digest? Break that one too (preimage and collision). Does this toy hash have the avalanche effect?
10. Suppose you have a hash function that outputs $k$-bit digests. Roughly how many random messages must you hash before you expect two with the same digest (a collision)? (See the Birthday Paradox Demonstration.) What does this give for MD5 (outputs 128 bits) and for SHA-256 (outputs 256 bits)? Does the birthday trick help you find a preimage?

Reminder: fill out the poster group form about poster groups (the link was in the last daily post).

Today’s lecture notes: Wednesday, September 23rd (also on the Notes/Videos page) — square roots and factoring, Miller-Rabin, Fermat factoring, and the quadratic sieve.

Friday’s lecture (September 25th) is pre-recorded and already up: the video and notes are on the Notes/Videos page.

Solution to the Kolmogorov complexity proof of the infinitude of primes (last daily post): it is written up in the textbook, Section 3.7 (Primality Testing).

Solutions: solutions to the daily posts due September 16th, 18th, 21st and 23rd are now posted (Sep 16, Sep 18, Sep 21, Sep 23). All daily post solutions are collected on the Archive page.

Relevant Textbook Sections:

3.7.2 (Miller-Rabin Primality Testing), 3.8 (Factoring), 3.8.3 (The role of squares in factoring), 3.8.4 (The quadratic sieve method), 3.6.3 (Short plaintext attack).

To Do:

1. Use the Miller-Rabin primality test with $a=2$ to determine if $n=90751$ is composite or probably prime. Show your steps.
2. If it comes up probably prime, try it with $a=3$. Show your steps.
3. Next, possibly using the Miller-Rabin Tools, implement the Miller-Rabin primality test to test if $n = 3057601$ is composite or probably prime, using the base $99908$.
4. Use Fermat Factoring to factor $n=16080$. Show the steps.
5. I wish to factor $n=38191$. How do I do it, if I have the following info?
   1. $196^2 - n$ factors as $3^2 \cdot 5^2$
   2. $201^2 - n$ factors as $2 \cdot 5 \cdot 13 \cdot 17$
   3. $214^2 - n$ factors as $3^2 \cdot 5 \cdot 13^2$
   4. $227^2 - n$ factors as $2 \cdot 3^3 \cdot 13 \cdot 19$
   5. $229^2 - n$ factors as $2 \cdot 3 \cdot 5^3 \cdot 19$
   6. $241^2 - n$ factors as $2 \cdot 3^2 \cdot 5 \cdot 13 \cdot 17$
   7. $254^2 - n$ factors as $3^4 \cdot 5^2 \cdot 13$
6. The euler-phi function gives $\varphi(21733) = 21420$. Use this fact to factor $21733$. (Hint: if $n=pq$, then knowing $n$ and $\varphi(n)$ tells you both $pq$ and $p+q$, so $p$ and $q$ are the two roots of a quadratic you can write down.)
7. Factor $n=31861$ using the Quadratic Sieve Tools page to produce the relations you will need. You may need to expand your factor base or the number of relations the boxes produce.
8. If you got lucky and got a single relation that did it, can you instead find a pair or larger combination of relations that do it?
9. Many of the messages posted on the #ciphertexts channel during the RSA ciphertext chain were pretty small. Can you attack any of them using the “small message” attack demonstrated in class (the birthday attack on RSA: look for a collision between $c x^{-e}$ and $y^e$, which reveals $m = xy$)? See also the textbook, Section 3.6.3 (Short plaintext attack).
10. Optional: If you aren’t familiar with for loops and if statements in Python/Sage, please visit these super quick tutorials: Python: For Loops and Python: If Statements. Then play around with the Sage Sandbox to see if you can find Carmichael numbers. This might require writing a for loop in python.

Added Sept 25: solutions to this daily post (Miller-Rabin, Fermat factoring, factoring from relations and from $\varphi(n)$, the quadratic sieve, the small-message attack, and Carmichael numbers) are now posted: Solutions to Daily Due Sep 25.

Reminder: Class on Wednesday, September 23rd is also on Zoom. The link is in Canvas.

Today’s lecture notes: Monday, September 21st (also on the Notes/Videos page). I’ll post the video link on discord once Zoom finishes preparing the recording.

Relevant Textbook Sections:

3.7 (Primality Testing), 3.7.1 (Fermat Primality Testing).

To Do:

1. Using the modular arithmetic playground or other tools (such as the Sage Sandbox), find examples of $x$ and $y$ such that $x^2 \equiv y^2 \pmod{n}$ but $x \not\equiv \pm y \pmod{n}$. What do you notice about the $n$ for which you can find such examples?
2. IF YOU ARE IN 4440: Think about forming a group of 2-3 people for a poster. Read the poster info in the Posters tab above. Reach out on discord, in person, etc., if you like to find a group that way. Then fill in the poster group form with your poster group situation so I can find out who is working with who or who needs help finding a team.
3. IF YOU ARE IN 5440: You do an individual project instead of a poster. Send me an email with your thoughts on topic and your background and we can brainstorm.
4. Think about your topic.
5. Use the birthday paradox approximation formula (with the natural log e in it) to determine the minimal number of people who need to be in the classroom to have at least a 50% chance of a shared Ceres birthday. (You’ll need to look up how many earth days in a Ceres orbit.)
6. Use Fermat’s Primality Test to detect whether 2001 and 2003 are composite or probably prime. Show your work (but you can use a calculator like Sage for the exponentiation). If one of them is probably prime, then try a different $a$ and explain what you learn.
7. This problem outlines a proof that there are infinitely many primes from a CS perspective, using information theory (due to Chaitin). This proof is in the textbook, but the idea is to create it yourself without reading it there.
   1. Define the Kolmogorov complexity $C(n)$ of an integer $n$ to be the length of the shortest computer program that will output $n$ in decimal form. (For concreteness, you can fix any programming language.) For example, the program for $2701$ might simply be print('2701'). This gives a trivial upper bound on $C(n)$ of $O(\log n)$. Explain why.
   2. For the numbers of the form $n=10^t$, prove that $C(n)$ is bounded above by $O(\log \log n)$ by giving an actual computer program.
   3. Suppose there are only finitely many primes $p_1, \ldots, p_k$. The number $k$ is a constant. Show that for all $n$, $C(n)$ is bounded above by $O(\log \log n)$, by using unique factorization.
   4. Prove that there must exist $n$ having $C(n) \ge \log n$, by using a counting argument.
   5. Explain why this proves there are infinitely many primes.

Added Sept 23: solutions to this daily post (the $x^2 \equiv y^2$ hunt, the Ceres birthday problem, and Fermat’s test on 2001 and 2003) are now posted: Solutions to Daily Due Sep 23.

Reminder: Class on Monday, September 21st is on Zoom. The link is in Canvas.

Relevant Textbook Sections:

2.12 (ElGamal Encryption), 3.6 (RSA Encryption), 3.6.1 (RSA Example).

To Do:

1. Suppose Oscar (a “man-in-the-middle”) intercepts and can modify a ciphertext on its way from Alice to Bob in El Gamal. Suppose he replaces the ciphertext $(K,c)$ with $(K,sc)$ for some $s$ of his choosing. (Oscar doesn’t know any of the secrets, like the message or private keys, but he can modify things.) What message will Bob decrypt? This exercise shows that Oscar can manipulate the message in a predictable way, without knowing what the message is. This is called “malleability”. This is an “active” attack, meaning that Oscar interacts with the protocol (changes things which are being sent during the protocol). Can you think of a way to fight malleability? How could you modify El Gamal to prevent this attack?
2. An RSA ciphertext chain!
   1. If you need a review of RSA, check the textbook (Section 3.6, with an explicit example in 3.6.1). For what follows, the Sage Sandbox page should be useful, as may be the RSA Tools page. These pages show how to do operations like modular inverse, exponentiation, and euler phi function in Sage. You can use basic number theory functions in Sage to do all your computations.
   2. First, set up your public and private key.
      1. Choose two 8-decimal-digit primes and form their product $n$. You can get primes out of Sage using the next_prime() function. So pick a number in the ballpark you want (maybe using randint()) and use next_prime() to get the next smallest integer which is prime.
      2. Compute $\varphi(n)$. Note that euler_phi() will do this for you in Sage, but it’s better to use the formula (p-1)*(q-1) because at cryptographic size, Sage would not return an answer, since euler_phi(n) would try to factor n.
      3. Choose an encryption exponent $e$ that is positive and less than $\varphi(n)$.
      4. Compute your decryption exponent $d$. It’s possible this will fail (e.g., if $e$ is not invertible!). If this error gets annoying (depends on your $\varphi(n)$), you could try using next_prime() to get a likely invertible $e$. (Concept check: why is a prime $e$ more likely to work?)
      5. Keep $d$ safe (along with $p$ and $q$, $n$ and $\varphi(n)$, just in case) in a file on your computer. The $d$ is your private key information; be sure also to keep $p,q, \varphi(n)$ away from prying eyes.
      6. Reveal your public key $n$ and $e$ on the discord #public-keys channel (“My RSA Public Key Is (n,e)=(…,…)”).
   3. Create a secret message which is at most 6 letters long. It should answer “What’s something awesome?” Please don’t make it longer or this exercise won’t work.
   4. Turn it into an integer using the Text to Integer tool. (There’s an Integer-to-Text tool on the same page to undo this process.)
   5. Now find someone else who has posted their public key (the most recent one before yours), and encrypt your message to that person. Post it on the #ciphertexts channel for them (use @theirname to alert them). Note: this should be one residue modulo their public $n$.
   6. When someone posts a message for you, decrypt it and announce the result using discord’s “spoiler” feature.
   7. You can turn in on canvas a screenshot of your discord result(s).

Added Sept 23: solutions to this daily post (El Gamal malleability and the RSA ciphertext chain worked end to end) are now posted: Solutions to Daily Due Sep 21.

Relevant Textbook Sections:

2.12 (ElGamal Encryption) for review.

To Do:

1. Do the El Gamal ciphertext chain if you haven’t already (last daily post).
2. Suppose that $x^2 \equiv y^2 \pmod n$ but $x \not\equiv \pm y \pmod n$. Explain how this can help you factor $n$. Hint: Factor a difference of squares.
3. Look at the modular arithmetic playground. Try some different functions and look at the dynamical portraits. Now, click on the modulus and use the arrow keys to go through different moduli. Look for patterns and see if you can predict whether or not $n$ is prime, or anything about its factorization, from studying the patterns. Do certain patterns imply that the modulus is prime or composite?

Added Sept 23: solutions to this daily post (how $x^2 \equiv y^2$ factors $n$, and the patterns in the dynamical portraits) are now posted: Solutions to Daily Due Sep 18.

Reminder: Test 1 (Module 1) is in class on Wednesday, September 16th.

Relevant Textbook Sections:

2.12 (ElGamal Encryption), and everything in Module 1 for review.

To Do:

1. Review for Test 1! Click the Tests tab for the syllabus and review problems. The Practice Problems page now generates (with solutions) modular exponentiation, towers of exponents, baby-step giant-step, index calculus and Diffie-Hellman problems. There is nothing to hand in on canvas for this post.
2. Optional: El Gamal Encryption Chain! We will use the same prime and generator as we did for Diffie-Hellman ($p = 10^{15}+37$, $g = 2$). This is set up on the Diffie-Hellman Tools page. Do the following:
   1. If you have not already made a public key for Diffie-Hellman Key Exchange, then set up a Diffie-Hellman private and public key for yourself. Publish the public key on the #public-keys channel on discord. Note your public and private key down for safekeeping. If you’ve lost your private key, delete your old key and do this again.
   2. Choose an at most 6 letter word as a message. It should be a polite, recognizable english word, so the decrypter will be able to tell they’ve done this correctly. It should answer, in some fashion, the question “Best food?” Turn it into an integer using the Text to Integer tool. Make notes on paper.
   3. Find the Diffie-Hellman public key immediately before yours in the #public-keys channel (if this doesn’t exist, use the most recent public key), and use that public key to encrypt your word to that person. Keep notes on paper of the key steps.
   4. Post your ciphertext publicly for that person on the #ciphertexts channel. Use @username. It should consist of two numbers, which we called $(K, c)$.
   5. When you receive a message from someone on the channel, decrypt it. Hopefully it is an english word. If it is, yay! Respond on the channel to that person to tell them the decryption you got. Keep notes on paper of the key steps.
   6. Challenges for fun:
      1. Break someone else’s message! Use any algorithm. Let me know if you succeed on discord!
      2. Get your friend to send two messages to the same person using the same ephemeral key. Break this!

Added Sept 23: solutions to this daily post (the optional El Gamal encryption chain worked end to end, plus the two challenges: breaking a key by Pohlig-Hellman and baby-step giant-step, and the repeated ephemeral key) are now posted: Solutions to Daily Due Sep 16.

Reminder: Test 1 (Module 1) is in class on Wednesday, September 16th.

Relevant Textbook Sections:

2.10.3 (Index Calculus), 2.10.4 (Runtime), and for review, 2.10.1 (The Baby-Step Giant-Step Algorithm) and 2.12 (ElGamal Encryption)

To Do:

1. Reminder: the first test is in class on Wednesday, September 16th, 2026 (Module 1). See the Tests page for the syllabus and review problems.
2. Solutions to the last daily post (the parity of the discrete log, baby-step giant-step for $51 = 2^x \pmod{83}$, the tower $2^{(3^{2026})} \pmod{33}$, and the runtime analysis) are now posted: Solutions to Daily Due Sep 11. All daily post solutions are collected on the Archive page.
3. To Know: If you’re interested in the runtime of the Index Calculus, I have more detail in the textbook (Section 2.10.4). Additionally, here are some course notes that cover it in more detail (from Andrew Sutherland’s MIT course on elliptic curves). This may be an interesting topic for a graduate student project: runtime for index calculus and/or index calculus improvements mod $p$ and/or in other finite fields.
4. Solve the discrete logarithm problem for $p=131$, $g=2$, $h=17$, using the Index Calculus method. You may use the Index Calculus Tools and Sage’s modular arithmetic and plain arithmetic computations to avoid by-hand computations, but please solve the linear system by hand (i.e. choosing which equations to subtract from which etc.). Note: this is a randomized algorithm, so you will get different relations than someone else, or next time you run the tool. If you are not finding a very nice linear system, just try to get some more relations and pick simple manageable ones.
5. An awkward linear system. Keep $p = 131$ and $g = 2$, and write $L(a)$ for the discrete log of $a$ base $2$ (so $L(a)$ is only defined modulo $p - 1 = 130$). One relation the tool can hand you is $2^{14} \equiv 9 = 3^2 \pmod{131}$, which says $14 \equiv 2L(3) \pmod{130}$.
   1. Suppose you “divide by two” to conclude $L(3) = 7$. Check this by computing $2^7 \pmod{131}$. Is it $3$?
   2. Explain what went wrong. How many solutions $y$ does $2y \equiv 14 \pmod{130}$ have, and what are they? Which one is $L(3)$?
   3. Find the parity of $L(3)$ using the test from the last daily post (raise $3$ to the $65$th power modulo $131$). Explain how this picks out the right solution in part (2) without any further checking.
   4. Here are three more relations: $2^{8} \equiv 5^3$, $2^{12} \equiv 5 \cdot 7$, and $2^{38} \equiv 3 \cdot 7 \pmod{131}$. Use them to find $L(5)$, $L(7)$ and $L(3)$ without ever dividing by an even number (you will need an inverse modulo $130$), and check that your $L(3)$ agrees with part (3).
   5. In general, which integers are safe to divide by (i.e. multiply by an inverse) when solving relations modulo $p-1$?
6. Runtime comparison. The (heuristic) runtime of the Index Calculus modulo $p$, with a well-chosen factor base, is about $e^{\sqrt{\ln p \cdot \ln \ln p}}$ operations (Section 2.10.4), while Baby-Step Giant-Step takes about $\sqrt{p}$ operations.
   1. Compute both quantities (to two significant figures, in scientific notation) for a $20$-digit prime, a $40$-digit prime, and a $100$-digit prime.
   2. Suppose $10^{20}$ operations is the most an attacker can afford. About how many digits must $p$ have to be safe against Baby-Step Giant-Step? Against the Index Calculus? (Treat the two formulas as exact; the real constants are different, but the moral is the same.)
   3. Explain in a sentence why the Index Calculus is called subexponential: compare $e^{\sqrt{\ln p \cdot \ln \ln p}}$ with $p^{\varepsilon} = e^{\varepsilon \ln p}$ for a fixed $\varepsilon > 0$ as $p \to \infty$.
7. Remember to upload to canvas!