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.)

Remember, you should set aside a studious hour for this.  If you don’t finish everything in one hour, continuing now or catching up later or skipping things is at your discretion.  Here’s what you should do with your hour before Friday’s class:

1. For the course, we will use Sage Mathematics Software for computations.  Here’s a Sage worksheet that shows how to use Sage as a calculator for modular arithmetic.  Check it out (do each computation by hand and then compare to the computer output).  Note:  worksheets on the course website do not save your data.
2. Create an example modulo 10 of residues $a,b,c$ such that $a \not\equiv b \pmod{10}$ and $c \not\equiv 0 \pmod{10}$, but $ac \equiv bc \pmod{10}$.  Explain why this means you “can’t always cancel in modular arithmetic.”
3. Compute $10^{12} \pmod{11}$ by cleverness.  Check your answer with Sage.  Verify that $10 \not\equiv 10^{12} \pmod{11}$.  Explain why this shows you “can’t take mod up in the exponent”.
4. Find our course notes (link to overleaf document at top left of this site!), and do Concept Checks 2.10 and 2.11 (currently page 16).  You will need to create an overleaf account for the poster later, so now is a good time to do this.
5. Watch this video about modular dynamics (18:46).  The goal here is to remind you about injective/surjective/bijective functions and to get you thinking about modular arithmetic in a “dynamical” way, which will help form intuition for later in class.
6. Draw a “multiplicative dynamical portrait” for $x \mapsto 2x$ modulo $5$.  That means, draw the elements of $\mathbb{Z}/5\mathbb{Z}$ as dots and draw an arrow from each dot to what you get when you double it.
7. Draw a “multiplicative dynamical portrait” for $x \mapsto 2x$ modulo $6$.
8. What do you observe about these two situations?  For each one, is the function $f(x) = 2x$ mod $n$ injective, surjective, both or neither?
9. Contact me if you have any concerns about the class being recorded.  I *do not* want this to discourage anyone from speaking in class, so talk to me, I can edit the audio if needed.
10. Make it part of your daily (“lecturely”) routine to look over what has been done and catch up on anything missing.  Remember, the “Archive” tab above has all our materials day-by-day including notes.
11. FYI:  The best way to contact me is discord.  If you want to meet in person just let me know or come to office hours Wednesdays (see “About”).  I also have a calendar for one-on-one appointments (link in canvas/discord) but you may need to remind me to add some slots.

Before Wednesday’s class:

• • Get yourself set up on discord.  Before you use the invite link available in canvas, make sure your username is not offensive (I get a notification the moment you click the link).   Discord has channels where you can chat with each other, and message are public by default.  It also have a video/voice channel capability.  Please choose an alias on our server that is your first name and last initial or first name and last name (let me know of any concern).  The discord has me, our TA, and our class, that’s it.
  • Read carefully through each of the pages that is listed on the TOP menu bar of this website (About, etc.).  These constitute the syllabus for the course.
  • Note: the next activity is to watch a video and do an accompanying worksheet.  I strongly suggest working on this in groups, and collaborating on daily tasks with classmates in general.  Get to know your peers!  To that end, I’ve set two designated times to meet on discord to do the video with peers (totally optional):
    • • Monday August 26th at 9 pm
      • Tuesday August 27th at 6 pm
  • The main activity for this daily post is to watch my video “Modular Arithmetic: User’s Manual” (9:22 mins:secs) and do the accompanying self-check worksheet.  Please be sure to show your work on the last problem.  (Note: you don’t need to print; you can work on a separate sheet of paper if desired.)
  • You will track your work on daily posts using this evaluation form.  You’ll keep this all semester –you might want to print it out and clip it to your wall.  Give yourself a score for your work today.  You can always find the link to this file under “Notes/Videos” on the top bar.
  • After each daily post, there are two things for you to do:  first, update your daily evaluation worksheet (the bullet point above), and then second, upload a record of your work to canvas.    The record of your daily post activity should be an images/copy of your written work, and including a copy of your self-evaluation sheet as it stands currently (both sides).  This is so we have a record we can return to if anything gets lost (chances are non-trivial that some student will lose their sheet at some point).
  • I’m flexible about it as you get used to this “daily task” system.  Just try it out and let me know if there are any hiccups.  I’m here to answer questions.

Hello class and welcome!

I’m your professor, Dr. Katherine Stange.  A little about me.  My job as a professor is half teaching and half research.  My research is in number theory and cryptography, so I especially enjoy this course.  When I’m not working, I like to cycle up Flagstaff, or anywhere that is uphill.

I hope you’re going to find this class challenging but fun and exciting.  This class has some features I want to make sure you are aware of up front:

• The focus on the course is on the mathematical algorithms underpinning modern cryptography and cryptanalysis, mostly public-key cryptography, as well as some coding theory.  We will tie the algorithms we study to real-world implementations and events.  Topics will include basic number theory including elliptic curves and finite fields, current public-key cryptosystems, basic quantum computing and quantum cryptography, post-quantum (quantum-safe) cryptography, and coding theory.
• This is a mathematics course, and you will be expected to reason mathematically about mathematical objects, follow and understand proofs, know definitions, be able to reason out examples, predict the outputs of algorithms and computations, etc.   However, this course will not emphasize proof-writing.  You certainly do not need to be a math major, but you need to have some mathematical/analytical thinking skills.  There are few explicit mathematical pre-requisites, but linear algebra will help a lot.
• I will teach and expect some basic python programming, so we can implement algorithms.  This will be modular, so if you have coding skills already, you won’t need to “redo” your basic skills.
• I expect you to find 1 hr between each class for homework.  There will be “daily posts”:  per lecture assignments.  The rest of your study time will be discretionary and flexible.
• We will use discord.  Please plan to check discord and this website regularly for updates.  Things move fast.
• There will be a poster project in small groups.  This is a self-guided research project into a related topic in the course.
• Students taking 5440 (instead of 4440) will replace the poster project with more extensive individual projects.

To Do:

• To learn all about the course, examine the tabs in the header menu.  These tabs together form the syllabus.
• Log into canvas for access to the discord sign up link.