1. On the archive page above, you can look at test solutions.  Please make sure your grades are correct.
2. Retakes:  You will have an opportunity to improve your grade on the first test.  Here’s how it works.  You may retake one of the 10 point problems in Part B that you attempted.   That means solving a similar problem.  The written retakes will be posted on canvas as soon as I can manage.
   1. 1. If you got 7 or higher on your problem, you will do a written replacement problem (I will post these).
      2. If you got 6 or lower, you will schedule to meet in person for a retake.  If you want to do this, use the calendar link on the canvas main page for appointments (15 minute slot).
3. To Know:  If you’re interested in the runtime of the Index Calculus, I have more detail in my overleaf text.  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. To Do:  El Gamal Encryption Chain!  We will use the same prime and generator as we did for Diffie-Hellman.  This is set up on that tools page.  Do the following:
   • • • 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 on paper for safekeeping.  If you’ve lost your private key, delete your old key and do this again.
       • 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.
       • 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 four-letter word to that person. Keep notes on paper of the key steps.
       • Post your ciphertexts publicly for that person on the channel.  Use @username.  It should consists of two numbers, which we called (K,c).
       • 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.
       • For the canvas submission, show your notes from this work.  If you don’t get someone sending you a message in time, that’s ok, but keep an eye out and do the decryption stage when possible.
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!

1. Reminder!  We have a course textbook on Overleaf with examples of the algorithms we cover.  The table of contents should help you find anything, and I have been adding in solutions to some daily post problems there.
2. Here are solutions to the last daily post (link to appear shortly).
3. Reminder!  You should be filling out your own daily post tracking sheet.  Please attach a copy of that to the daily post submission today so we can take stock.
4. Use the Baby-Step-Giant-Step algorithm (and show all steps) to solve the discrete logarithm problem $34 = 3^x \pmod{113}$.  You may use Sage’s functionality to compute the lists, including the tools on the BabyStepGiantStep page if you want to (ask for help on discord if you need some explanation of the page), so it shouldn’t involve much work by hand.  But please present the solutions tidily and in a well-explained and well-labelled way (indicate where each term in each list comes from, not just the value you get), so the algorithm is evident.
5. Suppose I write the standard trial division algorithm for factoring an integer $n$.  That is, I loop through all integers $k$ less than $n$, and try dividing $n$ by $k$ to see if it divides evenly.  What is the runtime of this algorithm?  As a function of the size of the input to the algorithm (the input is the number $n$ written in binary notation), is this an exponential or polynomial algorithm, or something in between?
6. Explain why for trial division, to factor $n$, you actually only need to loop through integers $k$ less than or equal to the square root of $n$.  How does this change your runtime analysis?
7. Consider the discrete log problem $h = g^a$ modulo $p$.  Suppose you make two lists:  $g^x$ for random $x$ and $hg^{-y}$ for random $y$.
   1. 1. Explain how, if you get a collision, it results in a solution to the discrete log problem.  This algorithm is called the “Birthday attack” on discrete log.
      2. The Baby-Step-Giant-Step algorithm is a sort of “organized” birthday algorithm.  Explain why I say this.
      3. How long should you make these lists to expect a decent probability of a collision?
      4. With reference to the last part, what is the runtime of the birthday attack on discrete log?
8. If you are so inclined, try to break one of the ciphertexts on discord from our Diffie-Hellman Key Exchange.

1. For each of the following pairs of functions, determine if $f=O(g)$ and if $g=O(f)$.
   1. 1. $f(x) =|sin(x)|$ and $g(x) = 1/2$.
      2. $f(x) = 2^x$ and $g(x) = 3^x$.
2. Use exhaustive search or any method to determine $L_2(3)$ modulo $13$.  You can use Sage’s modular arithmetic functions such as the tables on this page.
3. It is a fact that $p=101$ is prime, and $2$ is a primitive root modulo $p$.  It is a fact that $L_2(3)=69$ and $L_2(5)=24$ modulo $p$.   It is also a fact that the integer factorization of $24$ is $24 = 2^3 \cdot 3$.  Using these facts, evaluate $L_2(24)$ modulo $p$ with minimal work (just combine the facts above).
4. A bit of math practice that shows that the parity (even or oddness) of the discrete log can be discovered easily.  Let $p$ be an odd prime number.
   1. 1. Show that if $ab \equiv 0 \pmod p$ then $a \equiv 0 \pmod p$ or $b \equiv 0 \pmod p$
      2. Use part (1) on the expression $(x+1)(x-1)$ to show that the only two solutions to $x^2 \equiv 1 \pmod p$ are $1$ and $-1$.
      3. Let $g$ be a primitive root mod $p$.  Show that $g^{(p-1)/2} \equiv -1 \pmod p$.  (This uses the previous part.)
      4. Suppose $h \equiv g^x \pmod p$ is given to you (but $x$ is not known).  Show how you can determine if $x$ is even or odd.  Hint: Raise the equation $h\equiv g^x \pmod p$ to the $(p-1)/2$ power and see what you get using the previous part.
      5. Note that $2$ is a primitive root modulo $11$.  Use the test above to determine if $x$ so that $2^x \equiv 5 \pmod{11}$ is even or odd.
      6. Check whether you are correct by finding $x$ (by any method).
      7. Comment on the runtime of this test for the parity of $x$.
      8. Comment on whether parity of a discrete log is well-defined modulo $n$.  Why is it ok for odd primes $p$?

All you need to do for your daily post today is prepare for Wednesday’s test.  Info on the “Tests” tab above, including review problems.  No need to hand in anything on canvas, it will just be a freebie.

1. Info:  The material from class is in course text Section 3.4.
2. 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.
3. 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).

1. Info:  the material from today’s class is in written form in the course text (link upper left), Sections 3.1-3.3.
2. If you didn’t have time on the last daily post, catch up on these exercises:
   1. Watch my video explaining the Euclidean Algorithm (14 minutes).
   2. Compute the gcd of 135 and 170.  Show all the steps of the algorithm, as in the video.
   3. Consider the equation $7x + 15y = 1$.  Find an integer solution to this equation using inspection or trial and error.
   4. 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!)
3. Compute the gcd of 183 and 105.  Show all the steps of the algorithm, as in the video.  Verify using the Sage Sandbox (link at left for whenever you need it).
4. Solve $183x + 105y = 3$ by expanding your work above into “recipe cards” as shown in class.  Here’s another video which explains this (~11 mins) in case you need a refresher.  Verify your answer using Sage’s command xgcd (Sage Sandbox).
5. Find the inverse of 35 modulo 61.  Use the extended Euclidean algorithm.  Verify your answer by multiplying out.
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.
7. Find a solution to 3x + 5y = 1 (using the algorithm from class, or by guessing one).
8. Now find infinitely many different solutions to 3x+5y = 1.  (Hint:  use questions 2 and 3 above)
9. If time remains:  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):
   1. 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.
   2. Show that, if $b < a/2$, then $b’ < a/2$.
   3. Show that, if $b \ge a/2$, then $b’ \le a/2$.
   4. 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).
   5. What is the runtime of the Euclidean algorithm?

1. Notice:  First test will be on Wednesday, September 18th, 2024
2. On canvas (Studio Tab), there’s a video called “Diffie-Hellman Key Exchange Exercise” (~ 16 min) [ EDIT: link here ], which is a tutorial to accompany the following exercise.  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.
3. 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):
   1. 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.
   2. 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.)
   3. 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.
   4. Use the Diffie-Hellman Tools (second box) to find a random secret a.  We’ll call this your secret key.  Keep it secret and SAVE IT, 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.)
   5. Compute $g^a$ using the Diffie-Hellman Tools third box appropriately (no need to do this by hand!) We’ll call this your public key.
   6. 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).
   7. 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).
   8. 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.”
   9. 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.
4. With what time remains (if any), watch my video explaining the Euclidean Algorithm (14 minutes).
5. Compute the gcd of 135 and 170.  Show all the steps of the algorithm, as in the video.
6. Consider the equation $7x + 15y = 1$.  Find an integer solution to this equation using inspection or trial and error.
7. 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!)

1. Write me a few sentences “check-in”; how do you feel the class is going?  What are challenges, what can I do to help with those?
2. Use successive squaring to compute $3^{133} \pmod{1009}$.  You can use a calculator for the multiplications/reductions, but show all steps of the algorithm.  If you learned about double-and-add (see last daily post), you can use that if you prefer.
3. Some fun modular arithmetic, part one:
   1. Verify that $7$ is coprime to $12$ (factor them both).
   2. Compute $\varphi(12)$.
   3. Explain what Euler’s theorem says about powers of $7$ modulo $12$.  Why did we check the last two things?
   4. Compute $7^{115} \pmod{12}$ by hand using Euler’s Theorem.  Calculator is ok for multiplications and reductions, but show all steps.
4. Some fun modular arithmetic, part two:
   1. Verify that $59$ is coprime to $26$ (factor them both).
   2. Compute $\varphi(26)$ (it’s important you get this right, check your answer with the Sage Sandbox (the euler_phi function is listed there)).
   3. Compute $59^{(7^{115})} \pmod{26}$ by hand (this may use the previous problem…..)
5. Use what you learned from the last few problems to compute $3^{(11^{200006})} \pmod{50}$ “by hand” (this will always mean calculator is ok for multiplications and reductions, but show steps).
6. Observe (verify) that $\varphi(15) = 8$ and $3^8 = 6 \pmod{15}$.  (You can check these on Sage or by hand or both.) This looks like it contradicts Euler’s Theorem.  Why is it ok?
7. Catch up on last daily post problems or any other studying.

1. In what follows, hand in as much as you got done on canvas.  Remember, an hour of effective, useful work is all I ask.
2. Quick review question:  What is the inverse of 7 mod 11?  What is the inverse of 7 mod 14?  (Watch for trick questions!)
3. For each of the following $n$, compute the set $(\mathbb{Z}/n\mathbb{Z})^*$ and therefore its cardinality $\varphi(n)$:  $n=12$, $15$,  $16$, $26$, $27$, $30$.
4. In class, we proposed a formula $\varphi(n) = n(1 – 1/p_1)(1-1/p_2)\cdots(1-1/p_s)$ when $n$ is a product of distinct primes $p_i$.  Verify this for $n = 15$ and $n=30$ by comparing to what is above.
5. Now use the examples above and/or your own examples to guess a formula for $\varphi(p^k)$ where $p$ is a prime and $k$ is a positive power.  Can you explain your formula?
6. Now use the examples above and/or your own examples to guess a formula for $\varphi(n)$ that’s totally general (for any $n$).  Can you explain your formula?
7. The remaining problems today may be more than fits in your 1 hr.  You can prioritize them in whatever order feels most useful to you, and save the others for your discretionary study time.  Do finish them eventually, though!
8. Practice and reasoning with modular arithmetic with a cryptography flavour.  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.  (The plaintexts don’t need to be english, they can just be any letters.)
9. Some abstract thinking about modular arithmetic.  Prove (explain your reasoning) that:
   1. 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)
   2. If $a$ is invertible, then some power of $a$ is $1$. (Hint: use the first part somehow.)
   3. 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.
10.  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.
    1. First, watch this video (6:09) which gives a general algorithm.
    2. Use the double-and-add algorithm of the video (by writing 148 in binary) to demonstrate an efficient way to compute $2^{148}$.
    3. Program it if you feel like it.
11.  Practice with modular arithmetic in the context of matrices, with a cryptography flavour.
    1. The Hill cipher (with 2×2 matrices) was used to encrypt the plaintext SOLVED to get the ciphertext GEZXDS.  (Two letters were encrypted at a time.)  Can you find the Hill cipher key?
    2. 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 (why isn’t encryption injective?)?

1. 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.
2. Check out this tool for making addition and multiplication tables modulo n.  Try it for n=5 and n=6.  Notice some patterns.  Keep it in mind as a useful tool for future.
3. Our first ciphertext chain!!
   1. Come up with a short (one word) answer to the question “What’s the coolest math?”  This is your plaintext.
   2. 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.
   3. Encrypt the plaintext with affine cipher (by hand, using the cryptography tools sheet if you like).  This gives you your ciphertext.
   4. Post your ciphertext on the discord channel #ciphertexts, along with the key.
   5. Choose the most recent user’s post (besides yours) from #ciphertexts, and decrypt it (by hand).
   6. 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).
4. 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.
5. 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!!)   Post the number of multiplications you have to do (but not your secret sauce) in the #daily-collaboration channel, as a sort of friendly competition.
6. Hand items #4,5 in on canvas as your record for today’s daily post.
7. If needed, review injective, surjective, bijective, invertible for functions.  Here’s a discussion that gets right to the point.  Know the definitions, know examples, know a function is invertible if and only if it is bijective, and know that for a function from a finite set to itself, injective, surjective and bijective are equivalent.  (To really see why this is true, try to build a function from $\mathbb{Z}/5\mathbb{Z}$ to itself that is only injective or only surjective.)