%%% Document Class

\documentclass[11pt]{letter}
\usepackage[margin=1in]{geometry}


%%% Packages

\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{mathtools}


%%% Variables

\newcommand{\courseName}{Math 480A2}
\newcommand{\hwNumber}{6}
\newcommand{\hwDueDate}{October 6, 2022}


%%% Definitions

\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}

\renewcommand{\implies}{\rightarrow}
\renewcommand{\iff}{\leftrightarrow}

\renewcommand{\vec}[1]{\mathbf{#1}}


%%% Document

\begin{document}

\begin{center}
	{\large \courseName, Homework \hwNumber}\\
	Due \hwDueDate\\
\end{center}

{\small \textit{Homework is graded out of a total of 10 points.  Collaboration is permitted, but you must list all coauthors on a problem's solution at the top of the page, and your writing must be your own.}}

\vspace{5mm}

\textbf{Problem 1.} (3 points) Consider an elliptic curve group $E$ over the finite field $K = \ZZ / 5 \ZZ$.  What are the possible sizes of $E$ according to Hasse's inequality?  For each of these possible sizes, list the groups $E$ might be, presented as a cyclic group or sum of two cyclic groups, as in the structure theorem discussed in class.

\vspace{3mm}

\textbf{Problem 2.} (3 points) Describe an elliptic curve group $E$ over $K = \ZZ / 5 \ZZ$ by giving a short Weierstrass equation for $E$, listing the points of $E$, and giving an addition table for the elliptic curve group operation $+$ on $E$.  How can $(E, +)$ be written as a cyclic group or sum of cyclic groups?  (\textit{Hint:} for the prime field $\ZZ / p \ZZ$, elliptic curve groups exist having any size in the range given by Hasse's inequality.)

\vspace{3mm}

\textbf{Problem 3.} (2 points) Prove that a) the function $f(x) = \log(x)$ is $O(x)$, and b) the function $g(x) = 5,000 x^2 + 10,000 x$ is $O(x^2)$.

\textbf{Challenge.} (1 bonus point) Prove that the function $f(x) = e^{\sqrt{x}}$, defined on the nonnegative real numbers $\RR_+$, is super-polynomial, but sub-exponential.

\vspace{3mm}

\textbf{Problem 4.} (2 points) Compute the discrete logarithm $\log_{12}(91)$ in the group $G = (\ZZ / 101 \ZZ, +)$ of integers modulo 101 under addition.

\end{document}