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.