Due Friday, Sept 8th, 2023:

  1. I’ve updated the discord link in canvas if anyone still needs it (it last one week each time).
  2. In what follows, hand in as much as you got done on canvas.  Remember, an hour of effective, useful work is all I ask.
  3. Quick review question:  What is the inverse of 7 mod 11?  What is the inverse of 7 mod 14?  (Watch for trick questions!)
  4. 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})^*$.
  5. 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.
  6. 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.
  7. For remaining time (if any), you have two fun options, pick whichever seems like more fun to do first/at all:
      1. OPTION A:   Practice with modular arithmetic in the context of matrices, with a cryptography flavour.
          1. Read about Hill cipher.  (We mentioned it briefly Friday in class).
          2. 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.
          3. 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?
      2. 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.
          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.