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

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{listings}
\usepackage{xcolor}

\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
 
\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},   
    commentstyle=\color{codegreen},
    keywordstyle=\color{magenta},
    numberstyle=\tiny\color{codegray},
    stringstyle=\color{codepurple},
    basicstyle=\footnotesize,
    breakatwhitespace=false,         
    breaklines=true,                 
    captionpos=b,                    
    keepspaces=true,                 
    numbers=left,                    
    numbersep=5pt,                  
    showspaces=false,                
    showstringspaces=false,
    showtabs=false,                  
    tabsize=2
}
 
\lstset{style=mystyle}
\lstset{language=Python}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}


\begin{document}
\headers{Math373}{Homework 12}{Due Wed, Apr 20, 2022}

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

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

\makeatletter
\def\@oddfoot{}
\makeatother

\newcommand{\K}{\mathcal{K}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\ZZ}{\mathbb{Z}}
\renewcommand{\O}{\mathcal{O}}

\newcommand{\ord}{\mathrm{ord}}
\newcommand{\F}{\mathbb{F}}
\renewcommand{\poly}[1]{\mathbf{#1}}

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

\begin{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 exponent.  What should Bob send to Alice?
    \item Alice sends $A = (18, 17)$ to Bob.  Compute Alice and Bob's shared secret.
    \item \textbf{[Challenge (optional)]} Find Alice's private exponent $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}

\item Given polynomials $\poly{a}$ and $\poly{b}$ in $\F_{11}[x]$, find $q,r\in\F_{11}[x]$ such that $\poly{a} = \poly{q}\cdot \poly{b} + \poly{r}$ and either $\poly{r} = 0$ or $\deg(\poly{r}) < \deg(\poly{b})$.
\begin{enumerate}
	\item $\poly{a} = x^2 + 2x + 1$, $\poly{b} = x^3$
	\item $\poly{a} = x^3$, $\poly{b} = x^2 + 2x + 1$
	\item $\poly{a} = 3x^4 - 7x + 1$, $\poly{b} = x^3 + 5x^2 - 4$
	\item $\poly{a} = x^3 - x^2 -3x + 1$, $\poly{b} = 7x^2 + 4x - 3$
\end{enumerate}



\end{enumerate}
\end{document}
