To Do:

1. Solutions to the last daily post (the one due today) are now posted: Solutions to Daily Due Aug 28. Check your work against them. All daily post solutions are also collected on the Archive page.
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. 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.)
5. 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.
6. 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?)?
7. If it sounds fun, 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.
8. Remember to upload to canvas!