Due Wednesday, August 31st

For Wednesday:

  1. Remember that you only need to spend 1 hour.  If you get stuck on a problem, don’t spin your wheels; try some others instead and sleep on it.  You can come back to things.  I will post full solutions for these.
  2. Here are some solutions to the last daily post, which you should compare to your own answers from last time.
  3. 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})^*$.
  4. Another ciphertext exchange on discord!
    • Use Hill cipher to encrypt the answer to the question “What is your favourite vegetable?”  You can use some Hill Cipher tools here, to avoid by-hand computations.  Or you can write your own encryption/decryption program.  You can choose your own (valid!) key.
    • Post your key and ciphertext.  Use someone else’s key & ciphertext to get their plaintext and announce the result.  There’s a #ciphertexts channel for this.
  5. 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.
  6. 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?
  7. Prove that
    • 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$)
    • if $a$ is invertible, then eventually you will get a $1$
    • Remind yourself how to use the Multiplicative Dynamics tools.  Can you find an example where you never get a $1$ in that list?