%%% 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}