If you weren’t happy with your Module 1 grade, don’t despair! There is an opportunity to replace one grade from among the Part B questions you attempted (four questions each worth 10 points):
If you wish to replace a grade of 7, 8, or 9, I will provide a similar problem and ask you to hand in a solution on canvas. I will announce this after I have finished the in-person replacements for other students.
If you wish to replace a grade less than or equal to 6, then we will meet in person, and I will ask you to solve a similar problem. If you wish to do this, then please schedule a time with me (zoom or in person). This time can be anytime in the next week or so, but you must contact me to schedule it before Wednesday. Just email/DM me to set this up.
Your Module 1 test was handed back Monday and solutions are on the “Archive” tab above. Please take a look through these and make sure you understand how to do the problems and what your mistakes were.
Please compare last daily to the solutions here. Make sure you understand and correct your previous work.
Try out this Chinese Remainder Theorem problem, by hand: x = 3 mod 244 and x = 17 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. Hand this in on the dropbox.
Use any remaining time to catch up on past daily posts, or 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).
Find the inverse of 35 modulo 61. Use the extended Euclidean algorithm.
What if we want to solve 3x + 5y = 0? The zero is the weird part. Then we don’t use the Euclidean algorithm.
Give one solution by inspection (just find a clever one).
Now give another one different from the first.
Now give infinitely many.
Find a solution to 3x + 5y = 1 (using the algorithm from class, or by guessing one).
Now find infinitely many different solutions to 3x+5y = 1. (Hint: use questions 2 and 3 above)
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)$ as on the last daily post, then we get $(a’,b’)=(b,a-b)=(105,78)$ at the next step.
Show that, if $b < a/2$, then $b’ < a/2$.
Show that, if $b \ge a/2$, then $b’ \le a/2$.
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 (so, it may have decreased more than that).
Compute the gcd of 135 and 170. Show all the steps of the algorithm, as in the video.
Compute the gcd of 183 and 105. Show all the steps of the algorithm, as in the video.
Consider the equation $7x + 15y = 1$. Find an integer solution to this equation using inspection or trial and error.
Using the previous problem, tell me the inverse of $7$ modulo $15 and the inverse of $15$ modulo $7$. (This should require no computation, just look at the previous problem and have an aha moment!)
Wednesday is your test! Information, including suggested review, will shortly be on the “Tests” tab above.
In class on Monday, we covered Euler’s Theorem and El Gamal. To make sure you are ready for the test on these topics, here are some exercises with solutions (after the page break). You should do them without the solutions, and then only afterward compare to the solutions (of course).
I will have extra office hours Tuesday 12-1, in my office (Math 308).
Note! We have our first in-class test on Wednesday. More information (specific topics) is available under the “Tests” tab of this site.
In preparation for the test, the best thing to do with your hour this weekend is to go over the worksheets from last week. Each of them has solutions (all of them on the “Archive” tab), and you should make sure you understand these. One way to verify you understand is to try to re-do the sheets without looking at the solutions. This is great practice for the test.
Please hand in Friday’s worksheet on canvas in the dropbox for this daily post.
In class Friday, you will be working together to do an example of the index calculus. There’s a video on canvas entitled “BONUS VIDEO: Index Calculus” for you to watch before class. This is very important (otherwise you’ll be lost in class).
The video is around 30-35 minutes. While watching the video, pause and rewind as needed and take your time.
Bring a laptop or tablet to class to use the website Sage tools.
After you are finished, with what time remains, try to recreate the video example. You can use the Index Calculus Tools here (as I did in the video) and they generate relations randomly, so you will end up with a slightly different computation, but it should lead to the same result.
Important: in class on Wednesday we will be doing a worksheet based on the material from the videos below, so watching these before class is essential. Also bring a device (computer or ipad) to class to use the Sage tools during class.
Watch the video on canvas about Baby-Step-Giant-Step algorithm (~15 mins) under Media Gallery, titled “BONUS VIDEO: Baby-Step-Giant-Step” (note: it’s clips from a previous semester). This teaches the Baby-Step-Giant-Step Algorithm. Lecture notes.
Watch the video on canvas about Big Oh notation (~15 mins) under Media Gallery, titled “BONUS VIDEO: Big Oh”. (note: it’s a clip from a previous semester). This teaches the definition of Big Oh and begins to discuss runtimes. Lecture notes.
Watch the video on canvas about Runtimes (~10 mins) under Media Gallery, titled “BONUS VIDEO: Runtimes”. (note: it’s a clip from a previous semester). This continues examples of runtime analysis. Lecture notes.
Bring a device (computer or ipad) to class to use the Sage tools during class.
On canvas (Media Gallery Tab), there’s a video called “BONUS VIDEO: 2023-09-08 (Diffie Hellman Key Exchange in Practice)” Please watch this (~ 20 min) video. In the video, I demonstrate how to use the course website tools (on this website) to put your Diffie-Hellman public key up on the discord server, and send a message to someone there. Here are the written notes from that video.
Here are the full written instructions: you will perform a Diffie-Hellman Key Exchange in order to send a message to someone. Big picture: you’ll do a Diffie-Hellman Key Exchange to make a shared secret and then use that shared secret as a key for a very simple encryption (a sort of Caesar Cipher or One-Time Pad):
Create a secret message which is at most 6 characters long. It should answer “Why CU?” Please don’t make it longer or this exercise won’t work.
Turn it into an integer using the Text to Integer tool. (This turns it into an integer by writing the letters in ASCII and making an integer base 255 with those digits. There’s an Integer-to-Text tool on the same page to undo this process.)
We will use prime $p=10^{15}+37$, and its primitive root $g=2$. The first box in the Diffie-Hellman Tools page will initialize this modular ring for you.
Use the Diffie-Hellman Tools (second box) to find a random secret a. We’ll call this your secret key. Keep it secret, maybe in your underwear drawer. (Joking! — actually safer if you copy it into a text file on your computer, because if you write it by hand you’ll make an error.)
Compute $g^a$ using the Diffie-Hellman Tools third box (no need to do this by hand!) We’ll call this your public key.
Announce your public key on discord #public-keys. Be sure to explain this is your “Diffie Hellman Public Key” (there will be other types later).
Find someone else’s public key ($g^b$) on discord (the most recent public key on the #public-keys channel is best, so everyone gets to have part of the fun). Let’s call that other person Bob. Use it to generate your shared secret ($g^{ab}$) with Bob (you’ll need your secret key for this). Again, you can use the third box in the Diffie-Hellman Tools page to do the computations (no need to work by hand).
Add the shared secret to your message mod p. Announce the result on discord in the #ciphertexts channel as the secret message for Bob. Include your public key for them, because they will need it. You post might look like “My Diffie-Hellman message for @soandso is X.”
When someone sends you a secret message, figure out how to decrypt it and announce the result (so you can check it worked!). You may need to use the Diffie-Hellman Tools and the Text to Integer converter.
Please bring a device to class (laptop or ipad) that can use the course website Sage tools. We will be doing some work together in class in groups.
Check out last day’s solutions:
The inverse of 7 mod 11 is 8, since 7*8 = 56 which is 1 more than 55. One way to get Sage to compute this is Mod(7,11)^(-1).
The inverse of 7 mod 14 was a trick question! It has no inverse, since 7 and 14 share a prime factor.
You can verify your euler phi functions by the Sage command euler_phi(26), which returns 12. We have $\varphi(12)=4$, $\varphi(26)=12$, $\varphi(27) = 18$.
For the problems about $1, a, a^2, \ldots$, I essentially used/discussed this in lecture today, but feel free to ask more questions.
If you did some Hill Cipher problems on the last daily post, check out some exercises and solutions I’ve added to the overleaf notes, which included those problems.
I’ve updated the discord link in canvas if anyone still needs it (it last one week each time).
In what follows, hand in as much as you got done on canvas. Remember, an hour of effective, useful work is all I ask.
Quick review question: What is the inverse of 7 mod 11? What is the inverse of 7 mod 14? (Watch for trick questions!)
Compute the Euler phi functions $\varphi(12)$, $\varphi(26)$, $\varphi(27)$. For each of these $n$, verify your answer by computing the set $(\mathbb{Z}/n\mathbb{Z})^*$.
If the affine cipher key $(\alpha, \beta)$ is `badly chosen’ (i.e. $\alpha$ may not be invertible), then bad things can happen. Find an example where two different plaintexts encrypt to the same ciphertext.
Some abstract thinking about modular arithmetic. Prove (explain your reasoning) that:
If you take successive powers of $a$ mod $n$, i.e. $a,a^2,a^3,a^4,a^5,\cdots$, that eventually you will get a repeat (the same residue will appear more than once, e.g. $a^2$ might equal $a^7$). (Hint: finiteness)
If $a$ is invertible, then some power of $a$ is $1$. (Hint: use the first part somehow.)
Can you find an example residue $a$ modulo $n$ for some $a$ and $n$ where no power of $a$ is ever $1$? You might want to mess around with the various Sage tools on this site.
For remaining time (if any), you have two fun options, pick whichever seems like more fun to do first/at all:
OPTION A: Practice with modular arithmetic in the context of matrices, with a cryptography flavour.
Read about Hill cipher. (We mentioned it briefly Friday in class).
Can you find the Hill cipher key? The Hill cipher (with 2×2 matrices) was used to encrypt the plaintext SOLVED to get the ciphertext GEZXDS.
Consider Hill cipher with the matrix $$\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$$ modulo $26$. Can you find two plaintexts that encrypt to the same ciphertext? (The plaintexts don’t need to be english, they can just be any letters.) What’s wrong with this matrix?
OPTION B: Learn a useful new algorithm! The Double-And-Add algorithm allows for fast exponentiation, among other things; it’s a sort of refinement of successive squaring.
Check out this tool for drawing pictures of the function $f(x)=ax \pmod{n}$. Try it for $n=5$ and $n=6$ with different $a$’s. Figure out what it is doing.
Come up with a short (one word) answer to the question “What’s the coolest math?” This is your plaintext.
Choose a key $(\alpha,\beta) \in (\mathbb{Z}/26\mathbb{Z})^2$ . Make sure you choice is suitable as a key, as we discussed in class.
Encrypt the plaintext with affine cipher (by hand, using the cryptography tools sheet if you like). This gives you your ciphertext.
Post your ciphertext on the discord channel #ciphertexts, along with the key.
Choose the most recent user’s post (besides yours) from #ciphertexts, and decrypt it (by hand).
Post the answer in the form “So-and-so thinks the coolest math is….”. Use discord’s “spoiler” feature to hide your answer, in case other students want to practice, or end up using the same ciphertext (this never works quite perfectly).
Suppose you eavesdrop on your little sister’s communications, and she is using affine cipher. Her ciphertext is CRWWZ. You know she starts every message she writes with “HA” (she’s weird that way). Decrypt the message. Explain how you did it.
Come up with the fastest way to compute $3^{519}$ modulo $11$ by hand. That is, count the multiplications you need to do, and try to minimize that number. It should be doable by hand (i.e., don’t do 500+ multiplications!!) (Hint: think back to our puzzle at the end of class.)
Hand items #4,5 in on canvas as your record for today’s daily post.
The following video (17:26) I made discusses the proof of our “main theorem” from today that multiplication and addition “work” mod n. The goal of this video for you, here and now, is to understand why it works, and how math formalism guarantees the math we are using is “safe and correct”. If time remains, watch this; otherwise save for later when you have time.