\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{amsfonts}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{enumitem, url}
%\pagestyle{headings}

\usepackage{mathtools}

\newcommand{\0}{\mathbf 0}
\newcommand{\C}{{\mathbb C}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\diag}{\textrm{diag}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\normal}{\trianglelefteq}
\newcommand{\bmid}{\,\Big|\,}
\newcommand{\ds}{\displaystyle}
\newcommand{\lra}{\leftrightarrow}

\DeclareMathOperator{\GCD}{GCD}
\newcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}
\newcommand{\Legendre}[2]{\ds \genfrac{(}{)}{}{}{#1}{#2}}




\begin{document}

\thispagestyle{empty}

\begin{flushright}
  Your Name Goes Here
\end{flushright}


\begin{center}
  \textbf{Math 25}\\ Homework 6
\end{center}

\begin{enumerate}
\item \textbf{An encryption problem}

  \textbf{Background:} Let's use a 27-letter alphabet with $A \lra 0$,
  $B\lra 1$, \dots, $Z\lra 25$, space $\lra 26$.  We shall convert
  between alphabetic and numeric plaintext messages by a common
  scheme: encoding as a base 27 number with a certain block size, in
  our case 5.  We do this as follows: Suppose we want to convert the
  message `Groups are fun'.

  First we break up our plaintext message into blocks of length 5,
  padding the last block if necessary: `\texttt{Group}'
  `\texttt{s$\sqcup$are}' `\texttt{$\sqcup$funX}'.  Note we will not
  distinguish between upper and lower case, but this would easily be
  done by expanding the size of our alphabet.

  `\texttt{Group}' $\mapsto 06,17,14,20,15$; `\texttt{s$\sqcup$are}'
  $\mapsto 18,26,00,17,04$; `\texttt{$\sqcup$funX}'
  $\mapsto 26,05,20,13,23$, where the numbers represent the base-27
  digits. We now encode these as base 27 numbers:

  \vspace{-.2in}
  \begin{align*}
    \texttt{Group}&\mapsto 06,17,14,20,15\\ &\mapsto 27^4(06) + 27^3(17) +
                                              27^2(14)+ 27^1(20) + 27^0(15) = 3534018\\
    `\texttt{s$\sqcup$are}' &\mapsto 18,26,00,17,04\\ 
                  &\mapsto 27^4(18) + 27^3(26) + 27^2(00)
                    + 27^1(17) + 27^0(15) = 10078170\\
    \texttt{$\sqcup$funX} &\mapsto 26,05,20,13,23\\ 
                  &\mapsto 27^4(26)+27^3(05)+27^2(20)+27^1(13)+27^0(23)=13930835\\
  \end{align*}

  To proceed, we note that all the plaintext messages $P$ will satisfy
  $0\le P < 27^5 = 14,348,907$, so when choosing primes $p,q$ for our
  RSA modulus $n=pq$, we must make sure $n \ge 27^5$.

  \textbf{The exercise.}  Suppose we choose primes $p$ and $q$, so
  that $n = pq = 59753237$.  With the knowledge of those primes, we
  compute $\phi(n) = (p-1)(q-1) = 59737740$, and choose the common
  encryption exponent $e=2^{16}+1 = 65537$ (the last known Fermat
  prime).

  \begin{enumerate}
  \item Find the primes $p$ and $q$ using the idea from your notes.
    That is, do not just factor~$n$ (try to think that $n$ could have
    been a 600 digit number instead).  Finding $p$ and $q$ is not
    necessary to break the code, but reinforces that knowing $\phi(n)$
    is equivalent to factoring $n$.
  



  \item Find the decryption exponent.



  \item Using the base 27 encoding scheme as above, decrypt the
    message consisting of two blocks of numerical ciphertext, \newline
    i.e., given as $C = P^e\pmod n$: 10881312\quad 41465338.


  \end{enumerate}



\item Suppose that $m,n>1$ are coprime integers.  Prove that
  \[m^{\phi(n)} + n^{\phi(m)} \equiv 1 \pmod {mn}.
  \]



\item Show that 5 is a primitive root modulo 40487, but not one modulo
  $40487^5$.  Find a primitive root mod $40487^5$, and prove your
  result.  Feel free to use a computational tool like Sage to help
  with the computations.

\item Let $n > 2$ be an integer, and $a \in \Z$.
  \begin{enumerate}
  \item Suppose that $a^k \equiv a^\ell \equiv 1\pmod n$.  Show that
    $a^d \equiv 1\pmod n$, where $d~=~\gcd(k,\ell)$.
  \item Suppose that $a^{n-1} \equiv 1 \pmod n$ and
    $a^{(n-1)/q} \not\equiv 1 \pmod n$ for all primes $q \mid
    n-1$. Show that $n$ must be prime.
  \end{enumerate}



  Below is a table which gives each reduced residue mod 23 in terms of
  the primitive root~5.

  {\scriptsize
    \begin{tabular}[t]{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
      $k$&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21&22\\\hline
      $5^k$&5&2&10&4&20&8&17&16&11&9&22&18&21&13&19&3&15&6&7&12&14&1\\\hline
    \end{tabular}}


\item Use the information above to find all solutions to
  $3x^{10}\equiv 1\pmod{23}$.

\item Use the information above to find all solutions to
  $13^x \equiv 5\pmod{23}$.



\end{enumerate}

\end{document}


%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
