\documentclass[12pt,ifthen]{article}
\usepackage{url}
\usepackage{comment}

\newif{\ifshowsoln}
\showsolntrue
\newcommand{\und}{\_\_\_\_\_\_\_\_\_}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\tab}{\phantom{\qquad}}
\usepackage{amsmath}
\usepackage{amssymb}  % for \nmid

\begin{document}

\centerline{\textbf{HW 1 CMSC 456. Morally DUE Sep 21}}


{\textbf{NOTE- THE HW IS EIGHT PAGES LONG}}


\begin{enumerate}
\item
(10 points)
\begin{enumerate}
\item 
What is the day and time of the midterm?
\item
What is the day and time of the final?
\item
What is the {\it dead-cat policy}?
\end{enumerate}



\centerline{\textbf{GOTO NEXT PAGE FOR NEXT PROBLEM}}

\newpage


\item
(15 points)
Klingons use an alphabet of 30 letters.
Klingons want to use the affine cipher, so $x$ maps to $ax+b \pmod {30}$.
List out all of the values of $a$ can that Klingons can use.
List out all of the values of $b$ that Klingons can use.
How many pairs $(a,b)$ can be used?
(You can use DOT DOT DOT if it is REALLY obvious what you mean.)



\centerline{\textbf{GOTO NEXT PAGE FOR NEXT PROBLEM}}

\newpage


\item
(15 points)
Alice did not like doing the last problem! It was tedious! She worries that
Dr. Gasarch might ask about mod 100 or mod 1000 and then it will be really boring!

Write pseudocode for a program that will, on input $m$, output

\begin{itemize}
\item
the list of all $a$ such that $a$ can be used as the coefficient of 
$x$ in the affine cipher.
\item
the list of all $b$ such that $b$ can be used as the constant term 
in the affine cipher.
\item
the number of $(a,b)$ such that $ax+b$ can be used for the affine cipher.
\end{itemize}



\centerline{\textbf{GOTO NEXT PAGE FOR NEXT PROBLEM}}

\newpage



\item
(15 points)
Alphabet is $\{x,y\}$. $s\in \{0,1\}$, selected uniformly at random.
We use $x+s$ to mean $x$ shifted by $s$. Same for $y+s$. 

Alice wants to send TWO letters.
$m\in \{xx,xy,yx,yy\}$ is the message Alice wants to send.
$c$ is the ciphertext Alice sends.

\begin{itemize}
\item
If $m=xx$ then Alice sends $c=(x+s)(x+s)$.

\item
If $m=xy$ then Alice sends $c=(x+s)(y+s)$.

\item
If $m=yx$ then Alice sends $c=(y+s)(x+s)$.

\item
If $m=yy$ then Alice sends $c=(y+s)(y+s)$.

\item
Let $p_{xx}$, $p_{xy}$, $p_{yx}$, $p_{yy}$ be such that
$\Pr(m=xx)=p_{xx}$, etc.
Note that $p_{xx} + p_{xy} + p_{yx} + p_{yy}=1$.
WE ASSUME $p_{xx}$ etc are all NONZERO.
\end{itemize}


Give expressions for the following in terms of $p_{xx}$, $p_{xy}$, $p_{yx}$, $p_{yy}$.

\begin{enumerate}

\item
$\Pr[m=xx | c=xx]$

\item
$\Pr[m=xx | c=xy]$

\item
$\Pr[m=xx | c=yx]$

\item
$\Pr[m=xx | c=yy]$

\item
Use the results above to show that the cipher is insecure.

\end{enumerate}





\centerline{\textbf{GOTO NEXT PAGE FOR NEXT PROBLEM}}

\newpage

\item
(30 points)
This is a programming problem. You will write two programs. You will upload the second one for autograding.

In this problem we will look at the SHIFT cipher when you include not just letters, but also digits. So our alphabet will be
$\{a,b,c,\ldots,z,0,1,\ldots,9\}$.



\begin{enumerate}

\item
Your first program should take a text and
(1) eliminate all non-alphanumeric symbols and whitespace, 
(2) replace $a$ and $A$ with 1,
$\ldots$, replace $z$ and $Z$ with 26,
replace 0 with 27, replace 1 with 28, $\ldots$, replace 9 with 36.

\item
Write a program that, will given a text of numbers in $\{1,\ldots,36\}$
count how many of each symbol above there are.
So the output is a 36-long array of natural numbers.

\item
Write a program that, will,  given a 36-long array of natural numbers
$(f_1,\ldots,f_{36})$ will compute $F=\sum_{i=1}^{36} f_i$ and then output
the 36-long array of reals
$(\frac{f_1}{F}, \ldots, \frac{f_{36}}{F}).$


\item
Run your code on the sample.tex file (not hw01.tex) provided on the course webpage next to this homework, and have it calculate $\vec f = (\frac{f_1}{F}, \ldots, \frac{f_{36}}{F})$. Put the vector that you get as your answer to problem 5.


\item
Your second program should take a shifted text and also calculate $\vec f$.
You got a vector for unshifted text from part (d), call this $f'$. For $0\le i\le 35$ let $\vec f_i$ be $\vec f$ shifted by $i$ mod 36.
Print out a table of the 36 values.

$\vec f' \cdot \vec f_0$ 

$\vec f' \cdot \vec f_1$

$\vdots$

$\vec f' \cdot \vec f_{35}$

\item
Calculate the max of $\vec f' \cdot \vec f_i$ as $1\le i\le 35$
(it should be much larger than $\vec f' \cdot \vec f_0$. Don't print this.

\item
Use this to break the shift cipher. You should print the shift used to encrypt the input. Then, you should convert your values back into characters, and print the plaintext.

\item
Run your program on other math texts that have been shifted and see how well it works.

\end{enumerate}

\centerline{\bf GO TO NEXT PAGE FOR MORE ABOUT THIS PROBLEM!}

\begin{enumerate}

\item This problem will be autograded. There will be a separate assignment for this problem -- upload your program here. Specifically, the program that is uploaded should take in a shifted text from standard input and print parts (e) and (g) to standard output.
You only need to run parts (a) through (d) once, so you can hard-code the result from part (d) in the program you upload. But don't forget it to include part (d) in your manually-graded homework!

\item
You should upload a single file ending in .java, .py, .ml, .rb, or .c, corresponding to Java, Python3, OCaml, Ruby, and C respectively.
Ask on Piazza if you want more options.

Whatever you do, don't attack the server or exfiltrate the tests.

\item If for whatever reason you decide to handwrite this homework, it is ok to just put down the first few values. I'm not going to make you write down all 36. If you're typing this, you can just copy-paste your results from your program.

\item Separate each value with spaces, tabs, or newlines. Do not include symbols or whitespace in part (g). The autograder is case-insensitive. Floats should be printed to as many digits as you have: they will be rounded internally. Finally, please don't try to leak the test cases.

The input will be everything that goes into stdin. It will contain newlines, spaces, and irrelevant punctuation. Be sure that your program can handle these.

\item The test cases are the shifted LaTeX sources for real papers, up to 200 kilobytes each.

\end{enumerate}

\centerline{\bf GOTO NEXT PAGE FOR NEXT PROBLEM}


\newpage



\item
(15 points)
How many $x\in \{0,\ldots,11\}$ satisfy the equation

$$x^2 + 3x + 2 \equiv 0 \pmod {12}$$

No justification needed.
(Hence your grade will be either 0 or 15.)


\centerline{\bf GOTO NEXT PAGE}

\newpage

\item
(0 points but this is the most important problem on this entire HW set!!!!!)
Given $a,b$ we want to find if $a^{-1} \pmod b$ exists. 
\begin{enumerate}
\item
Look up {\it The Euclidean Algorithm} which is for this problem.
\item
Code up the algorithm (it will be used in many later assignments).
\end{enumerate}

DO NOT hand anything in, but DO THIS and I will, in the future, assume that you
did this and can use it within other assignments.


\end{enumerate}
\end{document}