\input{preamble}
\begin{document}

\begin{center}
  Fall 2021 -- Math 328K -- 55385
\end{center}
\section*{Homework 11}
\begin{center}
  \itshape due Tuesday, November 23, 14:00
\end{center}

\begin{problem}
  Here is a way to construct a primitive root modulo $p$. Let the prime decomposition of $\phi(p) = p-1$ be
  \[p-1 = q_1^{t_1} \cdots q_k^{t_k}\]
  where $q_1, \dots, q_k$ are distinct prime factors of $p-1$.
  \begin{enumerate}[a)]
  \item Let $a,b \in (\bZ/p\bZ)^\times$ such that $\ord(a)$ and $\ord(b)$ are coprime. Show that $\ord(ab) = \ord(a)\ord(b)$.
  \item Suppose that for each $i \in \{1,\dots,k\}$ we have $a_i \in (\bZ/p\bZ)^\times$ with $\ord(a_i) = q_i^{t_i}$. We showed in class that such an integer exists (in fact, we proved there are $\phi(q_i^{t_i})$ of these). Show that then $a = a_1 \cdots a_k$ is a primitive root.
%  \item Use this method to find a primitive root for $p = 29$.
  \end{enumerate}
\end{problem}

\begin{problem}
  Alice tries a few improvements to Caesar's cipher ($c_i = m_i + k$). Find the keys using the frequencies of letters and decrypt the ciphertexts. The spaces are only there for readability, they don't correspond to spaces in the plain text.

  {\itshape E is by far the most frequent letter in the English language (11.2\%), followed by A (8.5\%), R (7.5\%), I (7.5\%), O (7.1\%), T (7.0\%), N (6.7\%), S (5.7\%) and L (5.5\%).}
  \begin{enumerate}[a)]
  \item The text is encrypted with a Caesar cipher, and then the result is encrypted again with Caesar cipher, using a different key.
    \[\text{FTUEU EQCGU HMXQZ FFAME UZSXQ OMQEM DOUBT QD}\]
  \item The cipher $c_i = a m_i + b$, using two keys $a \in (\bZ/26\bZ)^\times$ and $b \in \bZ/26\bZ$. {\itshape (This one is a bit more difficult. It might be helpful to use a computer.)}
    \[\text{FQKVF ZQQUL ZLSNI VFZVZ QUVSH BWVIJ MAJZZ LWKVT VXZ}\]
  \item The cipher $c_i = a m_i + i$, using a key $a \in (\bZ/26\bZ)^\times$ (the indices start with $0$).
    \[\text{PMWJY LTDMF HVSXG NNBHE UILII FPBPE ECHZI TQLJF IUBBP}\]
%  \item Two ciphers of the kind a) applied in a row. That is, $c_i' = am_i + b$ and $c_i = a'c_i' + b'$, where the key consists of $a,a' \in (\bZ/26\bZ)^\times$ and $b,b' \in \bZ/26\bZ$. Is this cipher any more secure than a)?
%    \[\text{CYHTF HSYXK HTXBL HUNIX ACCJN THAPI XJAXJ GCVSX N}\]
  \end{enumerate}
\end{problem}

\begin{problem}
  Two texts were encrypted with a Vigenère cipher, both using the same key. The ciphertexts are


  We found out that the first message begins with HELLOBOB, and ends with ALICE, but we don't know what is in between.
  \[\text{ALLYY TUJRM ZKXAT BXAMP OIGKE LVRXS ZBCMH YNHLC VSIMV TVIX}\]
  \[\text{AHVRK FOKZJ EKTR}\]

  Decrypt the second message.
\end{problem}

\begin{problem}
  Let $[a]_p \in (\bZ/p\bZ)^\times$ be a primitive root. We want to show that either $[a]_{p^2}$ or $[a+p]_{p^2}$ is a primitive root in $\bZ/p^2\bZ$.
  \begin{enumerate}[a)]
  \item Let $n = \ord[a]_{p^2}$. Show that either $n = p(p-1)$ or $n = p-1$. The same holds for the order of $[a+p]_{p^2}$.

    {\itshape Hint: Show that $n \mid p(p-1)$ and $p-1 \mid n$.}
  \item Show that at least one of $[a]_{p^2}$ and $[a+p]_{p^2}$ is not a solution of the equation $x^{p-1} = 1$, and is therefore a primitive root.
  \end{enumerate}
\end{problem}

\end{document}
