\documentclass[11pt]{article}
\usepackage{amsmath, alltt, amssymb, xspace, times, epsfig}
\usepackage{amssymb}

\setlength{\evensidemargin}{0in} \setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in} \setlength{\textheight}{8.5in}
\setlength{\topmargin}{0in} \setlength{\headheight}{0in}

\newcommand{\Zn}{\ensuremath{\mathbb{Z}_n}\xspace}
\newcommand{\Zns}{\ensuremath{\mathbb{Z}_n^*}\xspace}
\newcommand{\Zp}{\ensuremath{\mathbb{Z}_p}\xspace}
\newcommand{\Zps}{\ensuremath{\mathbb{Z}_p^*}\xspace}
\newcommand{\Zq}{\ensuremath{\mathbb{Z}_q}\xspace}

\newcommand{\smod}{\ensuremath{\mathrm{mod}\;}}

\newcommand{\DD}{\ensuremath{\mathcal{D}}\xspace}

\newcommand{\Gen}{\ensuremath{\mathsf{Gen}}\xspace}
\newcommand{\Enc}{\ensuremath{\mathsf{Enc}}\xspace}
\newcommand{\Dec}{\ensuremath{\mathsf{Dec}}\xspace}

\renewcommand{\Pr}{\ensuremath{\mathbf{Pr}}\xspace}

\newcommand{\PT}{\ensuremath{\mathsf{PT}}\xspace}
\newcommand{\CT}{\ensuremath{\mathsf{CT}}\xspace}
\newcommand{\Key}{\ensuremath{\mathsf{Key}}\xspace}
\newcommand{\PrivK}{\ensuremath{\mathsf{PrivK}}\xspace}
\newcommand{\eav}{\ensuremath{\mathsf{eav}}\xspace}

\newcommand{\CC}{\ensuremath{\mathcal{C}}\xspace}
\newcommand{\KK}{\ensuremath{\mathcal{K}}\xspace}
\newcommand{\MM}{\ensuremath{\mathcal{M}}\xspace}
\newcommand{\AAA}{\ensuremath{\mathcal{A}}\xspace}



\newcommand{\note}[1]{\textbf{Note for TA:} #1}\xspace

\begin{document}
%\author{Ninghui Li}
%\date{}
%\maketitle

\thispagestyle{empty}

\noindent \textbf{CS555: Cryptography\hspace*{\fill}Spring 2012}
\begin{center}
{\LARGE Homework \#3}
\end{center}

\paragraph{Due date \& time:} 10:30am on February 28, 2012.
Hand in at the beginning of class (preferred), or email to the TA
(jiang97@purdue.edu) by the due time.

\vspace*{-0.1in}\paragraph{Late Policy:} You have three extra days in
total for all your homeworks.  Any portion of a day used counts as one
day; that is, you have to use integer number of late days each time. If
you emailed your homework to the TA by 10:30am the day after it was due,
then you have used one extra day. If you exhaust your three late days,
any late homework won't be graded.

\vspace*{-0.1in}\paragraph{Additional Instructions:}
The submitted homework must be typed. Using Latex is recommended, but not required.

\begin{description}

 \item[Problem 1 (9 pts)]
For a finite abelian group, one can completely specify the group
by writing down the group operation table.

\begin{itemize}
 \item (4 pts)
(a) Write down group operation tables for the following finite abelian groups:
$(\mathbb{Z}_5,+)$, $(\mathbb{Z}_5^{*},\times)$

 \item (2 pts)
(b) Show that the group operation table for every finite abelian group is a Latin
square; that is, each element of the group appears exactly once in each row
and column.

 \item (3 pts)
(c) Below is an addition table for an abelian group that consists of the elements
$\{a, b, c, d\}$; however, some entries are missing. Fill in the missing entries.

\begin{center}
\begin{tabular}{c|cccc}
+ & a & b & c & d \\ \hline
a & a &   &   &   \\
b & b & a &   &   \\
c &   &   & a &   \\
d &   &   &  &   \\
\end{tabular}
\end{center}

\textbf{Hint: Use part (b) above.  Try to determine the identity element first.  Use the fact that if $ab=ac$, then $b=c$.}
\end{itemize}

 \item[Problem 2 (5 pts)]
Let $G := \{x \in \mathbb{R} : x > 1\}$, and define $a \star b := ab - a - b + 2$ for
all $a, b \in \mathbb{R}$. Show that:
\begin{itemize}
 \item
(a) $G$ is closed under $\star$;
 \item
(b) the set $G$ under the operation $\star$ forms an abelian group.\\
\end{itemize}

 \item[Problem 3 (5 pts)]
Solve the following using the Chinese Remainder Theorem:
 $$\left\{ \begin{array}{ll}
   x = 4 & \mod 5 \\
   x = 3 & \mod 7 \\
   x = 2 & \mod 11
 \end{array}
 \right.
 $$
Write out the intermediate steps.  \\

 \item[Problem 4 (6 pts)]
(Katz and Lindell.  Page 294.  Exercise 7.1)\\

 \item[Problem 5 (5 pts)]
(Katz and Lindell.  Page 294.  Exercise 7.5)\\

 \item[Problem 6 (5 pts)]
(Katz and Lindell.  Page 294.  Exercise 7.8)\\

 \item[Problem 7 (5 pts)]
(Katz and Lindell.  Page 190.  Exercise 5.4.)\\

 \item[Problem 8 (5 pts)]
(Katz and Lindell.  Page 190.  Exercise 5.5.)\\

 \item[Problem 9 (10 pts)]
(Katz and Lindell.  Page 190.  Exercise 5.12.)\\

 \item[Problem 10 (10 pts)]
(Katz and Lindell.  Page 108.  Exercise 3.16.)\\

 \item[Problem 11 (15 pts)]
(Katz and Lindell.  Page 108.  Exercise 3.20.)\\

 \item[Problem 12 (10 pts)]
(Katz and Lindell.  Page 109.  Exercise 3.21.)\\

 \item[Problem 13 (10 pts)]
(Katz and Lindell.  Page 109.  Exercise 3.22.)\\

\end{description}

\end{document}
