\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}
\newcommand{\ord}{\mathrm{ord}}
\newcommand{\priv}{\mathrm{priv}}
\newcommand{\pub}{\mathrm{pub}}

\begin{document}
\headers{Math373}{Homework 9}{Due Fri, Mar. 28, 2014}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\newcommand{\compicon}%
{%
	\begin{tikzpicture}[scale=0.15]%
		\draw[double] (0,0) rectangle (1,1) ;
		\begin{scope}[yshift=-5pt]
			\draw (-0.5, -0.5) rectangle (1.5, 0) ;
		\end{scope}
	\end{tikzpicture}
}


\makeatletter
\def\@oddfoot{}
\makeatother

\newcommand{\F}{\mathbb{F}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\C}{\mathcal{C}}

\noindent
\textbf{Directions:} Solve the following problems.  All written work must be your own.  See the course syllabus for detailed rules.

\begin{enumerate}

\item CRT: Uniqueness of solutions. Suppose that $u$ and $v$ are both solutions to the system of congruences
\begin{align*}
x &\equiv a_1 \pmod{m_1}\\
x &\equiv a_2 \pmod{m_2}\\
& \vdots\\
x &\equiv a_k \pmod{m_k}. 
\end{align*}
Prove that $u\equiv v\pmod{M}$.  Hint: how many tuples $(a_1, \ldots, a_k)$ are there such that $a_i \in \Z_{m_i}$ for each $i$?  If $u$ and $v$ were different elements in $\Z_M$ that both corresponded to the same tuple $(a_1, \ldots, a_k)$, what would happen?

\item Solve the following systems of congruences.
\begin{enumerate}
	\item \begin{align*}
		x &\equiv 18 \pmod{25}\\
		x &\equiv 7 \pmod{11}\\
		x &\equiv 16 \pmod{32}
	\end{align*}
	
	\item \begin{align*}
		17x &\equiv 8 \pmod{43}\\
		6x &\equiv  41 \pmod{55}\\
		5x &\equiv 4 \pmod{9}
	\end{align*}
\end{enumerate}

\item Alice and Bob wish to use the ElGamal cryptosystem to communicate, and they are having difficulty deciding on a prime/base pair $(p,g)$.  The pairs that they are considering are $(345601, 71482)$ (option A), $(516163, 482305)$ (option B), and $(177007, 145014)$ (option C).  Which option do you recommend for Alice and Bob, and why?

\end{enumerate}
\end{document}
