In what follows, hand in as much as you got done on canvas. Remember, an hour of effective, useful work is all I ask.
Quick review question: What is the inverse of 7 mod 11? What is the inverse of 7 mod 14? (Watch for trick questions!)
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$.
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.
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?
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?
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!
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.)
Some abstract thinking about modular arithmetic. Prove (explain your reasoning) 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$). (Hint: finiteness)
If $a$ is invertible, then some power of $a$ is $1$. (Hint: use the first part somehow.)
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.
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.
Use the double-and-add algorithm of the video (by writing 148 in binary) to demonstrate an efficient way to compute $2^{148}$.
Program it if you feel like it.
Practice with modular arithmetic in the context of matrices, with a cryptography flavour.
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?
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?)?