\documentclass[10pt]{article}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}

\usepackage{amsmath,amscd,amsthm,amsfonts,amssymb,enumerate}

\theoremstyle{definition}
\newtheorem{rem}{Remark}
\newtheorem{com}{Comment}
\newtheorem{defn}{Definition}
\newtheorem{exam}{Example}
\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{prop}{Proposition}

\renewcommand{\P}{\mathbb{P}^1}
\renewcommand{\k}{\kappa}
\renewcommand{\H}{\mathbb{H}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\M}{\mathfrak{M}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\CC}{\mathcal{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\G}[1]{\Gamma(#1)}
\newcommand{\GO}[1]{\Gamma_0(#1)}
\newcommand{\Gb}[1]{\bar{\Gamma}(#1)}
\newcommand{\PSL}[1]{\mathbf{PSL}_2(#1)}
\newcommand{\z}{\zeta}
\renewcommand{\t}{\theta}
\renewcommand{\r}{\rho}
\newcommand{\sfrac}{\genfrac{}{}{0pt}{}{}{+}}
\DeclareMathOperator{\deck}{Deck}
\DeclareMathOperator{\aut}{Aut}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\gal}{Gal}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\im}{Im}
\author{Bryden R. Cais}
\title{Math 575}
\begin{document}

\maketitle
\section{Elliptic Curves over $\F_p$}

As usual, denote by $\F_p$ the integers modulo $p$.  It is a field of $p$ elements every one of which is a root of
$x^p-x\equiv 0\mod p$.  Since $p=2,3$ are often difficult primes to deal with (for a slew of reasons) we shall assume
throughout that $p\geq 5$.  We have already studied quadratic equations over $\F_p$ and have seen that this leads to
many interesting ideas (quadratic residues and quadratic reciprocity, for example).  One interesting property of the set of
quadratic residues modulo $p$ is that it actually forms a \textit{group} under multiplication (of index $2$ in $\F_p^{\times}$).
As we shall see, the study of suitable \textit{cubic } equations over $\F_p$ leads to even more interesting results.

\begin{defn}[Preliminary]
    An \textbf{elliptic curve} over $\F_p$ (with $p\geq5$ as we shall \textit{always} suppose) is the set of $\F_p$ points $(x,y)$
    satisfying
        $$y^2=x^3+ax^2+bx+c.$$
\end{defn}

This may at first seem a little strange.  Considering solutions to cubic equations is natural enough, but why the $y^2$ and not just $y$?
In short, equations of the form $y=x^3+ax^2+bx+c$ over $\F_p$ aren't all that interesting, since, for example, they always have $p$ points
(one for every value of $x$).  So in some sense, having the $y^2$ is the first instance of when interesting things start to happen.  Now,
since $p\geq 5$, we can replace $x$ by $x-a/3$ to get (an equivalent in an appropriate sense) equation without the $x^2$ term.
So we can actually work with equations of the form $y^2=x^3+px+q$.  We need to be a little more careful, though.
Recall that the \textit{discriminant} of a quadratic polynomial $x^2+bx+c$ is $b^2-4c$, and that if this vanishes then (by the quadratic
formula, say) there is only one root of multiplicity 2.  In some ways, this is a \textit{bad} scenario.
So by analogy with our cubic, we require that the roots of $x^3+px+q$ be distinct (in some algebraic closure of $\F_p$), or, equivalently
that the \textbf{discriminant}
$$27q^2+4p^3$$
not vanish modulo $p$.

We are now almost to the correct definition.  Observe that a general line $mx+ny=b$ will intersect the locus of \textit{complex }points
satisfying $y^2=x^3+px+q$ at 3 distinct points.  To see this, observe that an intersection point is a root of
$$(\frac{b-mx}{n})^2=x^3+px+q,$$ which in general has three distinct roots in $\C$.  There are two exceptions to this.  The first is that
one point might have multiplicity $2$, and the line will be tangent at that point.  This isn't a problem though, as we know how to count ``with multiplicity.''
The other issue is that we might have $n=0$, in which case our line is vertical.  The only way to remedy this situation to force there to be three intersection
points is to think of a point ``infinitely far away'' lying on our curve, and think of any vertical line as intersecting this point.
This notion can be made precise by considering \textit{projective} equations, but we will stick with this intuitive notion.

We now give the correct definition of an elliptic curve over $\F_p$:
\begin{defn}[Actual]
    An \textbf{elliptic curve} $E$ over $\F_p$ is the set of $\F_p$ points $(x,y)$
    satisfying
    \begin{align}
        y^2=x^3+px+q,\label{def}
    \end{align}
    where $27q^2+4p^3\not\equiv 0\mod p$, together with the point $O$ ``at infinity,'' which any ``vertical'' line is thought of as
    intersecting.
\end{defn}

Note that vertical is in quotations above since it is rather hard to visualize graphs in $\F_p^2$.

\section{The Group Law}

It is not difficult to see that the line through any two points on $E:y^2=x^3+px+q$ intersects $E$ at a third point.  Indeed, Suppose that
$(x_1,y_1)$ and $(x_2,y_2)$ are two distinct points (with coordinates in $\F_p$) on $E$.  The line through these points
is given by
$$y=\left(\frac{y_2-y_1}{x_2-x_1}\right)(x-x_1)+y_1:=mx+b$$ so that every point of intersection with $E$ is a root of
$$(mx+b)^2=x^3+px+q,$$ that is, a root of
$$x^3-m^2 x^2+(p-2mb)x+q-b^2=0.$$  Recall that the sum of the roots of a cubic equation is equal to the negative of the coefficient of $x^2$, so that if
$(x_3,y_3)$ is the $x$ coordinate of the third point of intersection of the line through $(x_1,y_1)$ and $(x_2,y_2)$
then we have
$$x_1+x_2+x_3=m^2.$$  Thus, the third point of intersection is
\begin{align}
    x_3&=\left(\frac{y_2-y_1}{x_2-x_1}\right)^2-x_1-x_2\label{add1}\\
    y_3&=\left(\frac{y_2-y_1}{x_2-x_1}\right)(x_3-x_1)+y_1.\label{add2}
\end{align}
Observe that this point is on $E$ provided that $(x_1,y_1)$ and $(x_2,y_2)$ are: it has coordinates that are rational functions in $x_i,y_i$.
These formulae even make sense for $x_1=x_2$ and $y_1\neq y_2$ if interpreted correctly.  In this case, the slope of our line is infinite,
so we take the third point of intersection as the point $O$.  If $(x_1,y_1)=(x_2,y_2)$, it is natural to invoke some sort of limiting
process: namely, as the point $(x_2,y_2)$ on $E$ moves closer to $(x_1,y_1),$ the line joining them approaches the tangent line at
$(x_1,y_1)$, whose equation we can find by ordinary calculus.  In particular, the tangent line at $(x_1,y_1)$ is
$$y=\frac{\mathrm{d}y}{\mathrm{d}x}(x_1,y_1)(x-x_1)+y_1.$$
But by implicit differentiation, we have
$$2y\frac{\mathrm{d}y}{\mathrm{d}x}=3x^2+p$$
(and again you see why we avoid $p=2,3$) so that the line in question is
$$y=\frac{3x_1^2+p}{2y_1}(x-x_1)+y_1$$ so that our ``third'' point of intersection with $E$ is
\begin{align}
    x_3&=\left(\frac{3x_1^2+p}{2y_1}\right)^2-2x_1\label{add3}\\
    y_3&=\left(\frac{3x_1^2+p}{2y_1}\right)(x_3-x_1)+y_1.\label{add4}
\end{align}
Finally, we take the third point of intersection of the tangent line through $O$ to be $O$.  This ``definition'' can be justified,
and an intuitive version is just to apply the above formulae with $y_1$ ``infinitely large''.

So now we have a \textbf{binary operation}
$$E\times E\rightarrow E$$ given by
$$(a,b)\mapsto \{\text{the ``third'' point of intersection of the line though $a,b$ with $E$}\},$$
where we interpret this point as appropriate by the above discussion.  Anytime we have a set equipped
with a binary operation, the natural question to ask is whether or not our set forms a group under this operation.
The answer, for the moment, is no, since there is no identity element.  But we can easily fix this: for
$P,Q\in E$, let $R$ be the image of $(P,Q)$ under the above map.  Then we define
$$P+Q$$ to be the third point of intersection of the line through $O$ and $R$ with $E$.  It is not hard to see that
if $R=(x,y)$ then $P+Q=(x,-y)$, since the vertical line through $(x,y)$ intersects $E$ at $(x,-y)$.  This in conjunction
with our formulae (\ref{add1}--\ref{add4}) gives explicit algebraic equations for determining the coordinates of $P+Q$
given those of $P,Q$.  Moreover, a little thought will convince you that $O+O=O$ and that $P+O=P$ for any $P\neq O$ in $E$.
It is clear that $+$ is commutative.  The above considerations also show that the point $O$ acts as an identity
element and that every point of $E$ has an inverse.  What is not clear is whether or not the operation $+$ so defined
is \textit{associative}.

\begin{thm}
    The set $E$ forms a finite abelian group under $+$.
\end{thm}
\begin{proof}
    As mentioned above, it only remains to show associativity.  One can attempt to do this algebraically using the formulae (\ref{add1}--\ref{add4}),
    or directly from the geometric definition.  Both approaches are tedious.  See \cite{sil}.
\end{proof}

Let's look at some examples to get a feel for how the group of $\F_p$ points on an elliptic curve $E$ works.

\section{Examples}

\begin{exam}
    Let $E$ be given by $y^2=x^3+1$ and let $p=5$.  It is not difficult to find that the set of points on $E$ is
    $$O,(0,\pm 1), (2,\pm 3), (-1,0).$$
    Let us determine $(0,1)+(-1,0)=(x_3,y_3)$.  From (\ref{add1}) we have
    $$x_3=\left(\frac{0-1}{-1-0}\right)^2-(0)-(-1)=2$$ and hence
    $$y_3=-3.$$
    Let us now compute the multiples of the point $P=(0,1)$.  By (\ref{add3}) we have $2P=(x_3,y_3)$
    where
    $$x_3=0,\ y_3=-1.$$
    It follows that $3P=O$.  Similarly, for $Q=(2,3)$, we readily determine that
    $$2Q=(0,1)$$ and hence that $Q$ has order $6$.  It follows that the set of points of $E$ is isomorphic
    to $\Z/(6)$ and is generated by $Q$.  Indeed, one finds:
    \begin{align*}
        Q&=(2,3)\\
        2Q&=(0,1)\\
        3Q&=(-1,0)\\
        4Q&=(0,-1)\\
        5Q&=(2,-3)\\
        6Q&=O.
    \end{align*}
\end{exam}

\begin{exam}
    Next we explore the curve given by $E:y^2=x^3-7x+7$ over $\Z/(19)$.  We shall see later that curves of this form play an important role
    in the application of elliptic curves to factoring large numbers.  Observe that $(1,1)$ is on $E$.  Let us compute the
    multiples of $P=(1,1)$.  For this, we use the following (not so elegant but functional) PARI code:
\begin{verbatim}
mult(p,r,a,b,n)={
 x=((3*a^2+p)/(2*b))^2-2*a;
 y=-((3*a^2+p)/(2*b)*(x-a)+b);
 for(i=1,n,print([lift(Mod(x,r)),lift(Mod(y,r))]);m=(y-b)/(x-a);x=m^2-x-a;y=-m*(x-a)-b);
}
\end{verbatim}
which prints the multiples $2P,3P,\ldots (n+1)P$ of the point $P=(a,b)$ (and gives an error message when it tries to divide by $0$ in computing
the point at infinity if $(n+2)P=O$) on the curve $y^2=x^3+px+q$ taken modulo $r$.
We find in the case above ($p=-7,\ (a,b)=(1,1),\ r=19$)
    \begin{align*}
        P&=(1,1)\\
        2P&=(2,1)\\
        3P&=(16,18)\\
        4P&=(7,15)\\
        5P&=(8,8)\\
        6P&=(11,8)\\
        7P&=(13,2)\\
        8P&=(12,6)\\
        9P&=(15,3)\\
        10P&=(10,14)\\
        11P&=(0,11)\\
        12P&=(4,10)\\
        13P&=(4,9)\\
        14P&=(0,8)\\
        15P&=(10,5)\\
        16P&=(15,16)\\
        17P&=(12,13)\\
        18P&=(13,17)\\
        19P&=(11,11)\\
        20P&=(8,11)\\
        21P&=(7,4)\\
        22P&=(16,1)\\
        23P&=(2,18)\\
        24P&=(1,18)\\
        25P&=O
    \end{align*}
    This is pretty amazing for two reasons: first, given a single point on $E$, we can find (usually)
    many others by exploiting the group operation.  Second, we know that since $25P=O$, then the
    total number of points on $E$ is divisible by $25$.
\end{exam}

\begin{thebibliography}{10}
    \bibitem{sil} Silverman, J.  ``The Arithmetic of Elliptic Curves.''  Springer Verlag, N.Y. 1992.
\end{thebibliography}
\end{document}