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

\newif{\ifshowsoln}
\showsolntrue
\newcommand{\und}{\_\_\_\_\_\_\_\_\_}
\newcommand{\Z}{\mathbb{Z}}
\usepackage{amsmath}
\usepackage{amssymb}  % for \nmid
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}


\begin{document}

\centerline{\textbf{HW 3 CMSC 456. Morally DUE Sep 23}}


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


\begin{enumerate}


\item
(0 points)
READ the syllabus- Content and Policy.
READ my NOTES on  ciphers and on English.
What is your name?
What is the day and time of the first midterm?

\item
(25 points)
(This problem is based on material that you will see on Wed Sept 18.)


\begin{enumerate}
\item
(5 points)
Alice wants to compute $7^{81} \pmod {101}$.
Do this using repeated squaring. Show all work.
How many multiplications does it take?
\item
(5 points)
Alice notices that $81=3^4$.
So instead of using repeated {\it squaring} she decides
to use repeated {\it cubing}. Each cubing takes two multiplications
but there are less iterations. Compute $7^{81}$ using this. Show all work.
How many multiplications does it take?
\item
(8 points)
Give an algorithm that does the repeated cubing method
for the problem: given $a,n,p$, find $a^n \pmod p$.
Give a good upper bound on 
how many multiplications it takes as a function of $n$.
You CANNOT use O-notation at all. You CAN upper bound something like
$\floor{BLAH}$ by BLAH.
\item
(7 points)
Recall that for repeated squaring the number of multiplications
is 
$$\le \lg(n) + (\hbox{ Number of 1's in binary rep of $n$ })-1.$$
Give three examples of an $n\ge 99$ where the repeated-cubing
algorithm takes less mults than the repeated-squaring algorithm.
\item
(0 points) Why isn't repeated cubing used more often?
\end{enumerate}


\centerline{\textbf{GO TO NEXT PAGE}}

\newpage


\item
(25 points)
Alice and Bob are going to use the Affine Cipher.
They get to choose their alphabet size!
If the alphabet size is $n$ then they will pick
a number $a\in \{1,\ldots,n\}$ at {\it random} and then 
test if $a$ will work to be the coefficient of $x$.
If not, then try again.
If so then they will use
$a$ as the coefficient for $x$. (We are not concerned with
the picking of $b$.)
\begin{enumerate}
\item
(10 points)
Assume the alphabet size is 1000.
What is the probability that the $a$ they pick will work? Call this $p_{1000}$.
(Think about but do not hand in: what is the expected number of times they will need to pick an $a$?)
\item
(10 points)
Assume the alphabet size is 1001.
What is the probability that the $a$ they pick will work? Call this $p_{1001}$.
(Think about but do not hand in: what is the expected number of times they will need to pick an $a$?)
\item
(5 points)
Which of $p_{1000}$ and $p_{1001}$ is bigger? Based on this give some general advice on
what alphabet size to use if a prime size is not available.
\end{enumerate}


\centerline{\textbf{GO TO NEXT PAGE}}

\newpage

\item
(25 points)
We describe the {\it Randomized Affine Cipher}.
ALL arithmetic is mod 26.

Let 

$$S= \{(a,b) \mid 0\le a,b\le 25, \hbox{$a$ is rel prime to 26} \}$$

The key is a function $f$ from $\{0,\ldots,25\}\times \{0,\ldots,25\}$ to $S$. 
To send message $(m_1,\ldots,m_L)$ (each $m_i$ a character)
Alice does the following:
\begin{itemize}
\item
Pick random $r_1,\ldots,r_L\in \{0,\ldots,25\}\times \{0,\ldots,25\}$.
\item
For $1\le i\le L$ let compute $f(r_i)=(a_i,b_i)$.
\item
Send $(r_1,a_1m_1+b_1),\ldots,(r_L,a_Lm_L+b_L)$.
\end{itemize}

\begin{enumerate}
\item
(15 points)
Describe how Bob will, given 
$$(r_1,c_1),\ldots,(r_L,c_L),$$

decode the message.
(Note that Bob has the key $f$.)

\item
(10 points)
Alice and Bob are using the following key:
$f(x,y)=$ 
\begin{itemize}
\item
The first coordinate is the first number AFTER $x$ that is rel prime to 26
with the exception that $x=25$ yields $1$.
\item
The second coordinate is $y+1$ (all mod 26).
\end{itemize}

Alice want to send the message {\it clyde}.

Alice generates the following five random pairs to help her do this. They are

(2,5), (3,6), (10,2), (15,7), (25,0).

What does Alice send to Bob?

\end{enumerate}

\centerline{\textbf{GO TO NEXT PAGE}}

\newpage

\item
(25 points)
Alice and Bob are using the cipher on the Sept 9 slides, title
{\it Awesome Vig or Psuedo One-Time Pad}
EXCEPT that the mod is 2 digits long instead of 4 digits long.

Eve is sure that the word ERIK will be in the plaintext. 

Eve looks at every 4-long sequence in the ciphertext and guesses 
that they decode to ERIK and sets up equations.

Eve sees ABCD.  

\begin{enumerate}
\item
(7 points)
Write down (but do not solve) the equations she will try to solve to find how the key is generated.
Show all work.
\item
(7 points)
What are the bounds on $M$?
\item
(11 points)
Find the values of $M$ that could possibly work, or show there aren't any.
\end{enumerate}


The following table will help you:

\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
A &   B &  C  & D  & E  & F  & G & H  & I  & J  & K  & L  & M \cr
\hline
01 & 02 & 03 & 04 & 05 & 06 & 07 & 08 & 09 & 10 & 11 & 12 & 13\cr
\hline
\end{tabular}

\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
N &   O &  P  & Q  & R  & S  & T & U  & V  & W  & X  & Y  & Z \cr
\hline
14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26\cr
\hline
\end{tabular}




\end{enumerate}

\end{document}