\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 13}{Due Fri. Apr. 25, 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}}
\renewcommand{\O}{\mathcal{O}}

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

\begin{enumerate}


\item Let $E$ be the elliptic curve given by $y^2 = x^3 -27x + 55$.  In class, we showed that 
\[ [(2,3)(3,1)](-1,-9) = [(-1,-9)](-1,-9) = (-1,-9)^2 = (34/9, 71/27) .\]
\begin{enumerate}
    \item Compute $(3,1)(-1,-9)$.
    \item Use part (a) to verify that $(2,3)[(3,1)(-1,-9)] = (34/9, 71/27)$.
\end{enumerate}

\item Let $E$ be the elliptic curve given by $y^2 = x^3 + 5x + 1$ over $\F_{19}$.  Compute the following.
\begin{enumerate}
    \item $(4,3)\O$.
    \item $(4,3)^{-1}$.
    \item $(4,3)(10,-5)$.
    \item $(4,3)^2$.
    \item $(4,3)^4$.
    \item $(4,3)^8$.
\end{enumerate}

\item Alice and Bob wish to share a secret using Elliptic Curve-based Diffie--Hellman.  They agree on the curve $E$ given by $y^2 = x^3 + 14x + 2$ over $\F_{31}$ and the base element $g=(12,10)$.
\begin{enumerate}
    \item Bob picks $b=10$ as his private key.  What should Bob send to Alice?
    \item Alice sends $A = (18, 17)$ to Bob.  Compute Alice and Bob's shared secret.
    \item \textbf{[Challenge]} Find Alice's private key $a$.  In other words, find $a$ such that $g^a = A$.  This is an instance of the Elliptic Curve Discrete Logarithm Problem (ECDLP).
\end{enumerate}

\end{enumerate}
\end{document}
