Elliptic Curves

Let $P=(a,b)$ be a point, not of order 2. Consider the rational function $g(X,Y)=(X-a{)}^k$ for some $k>0$. Then note $g(P)=0$. We say $g$ has a zero at $P$ of multiplicity $k$. On the other hand, if $g(X,Y)=1/(X-a{)}^k$ for some $k>0$, we say $g$ has a pole at $P$ of multiplicity $k$.

We can generalize this to all functions, so for example, if a function can be written in the form $(X-a{)}^{k}h(X,Y)$ where $h(a,b)\ne 0,\mathrm{\infty }$, then we have a zero of order $k$ if $k>0$, or a pole of order $-k$ if $k>0$.

Given an arbitrary function $g(X,Y)$, it may not be immediately obvious where the zeroes and poles are. Fortunately, there exists an efficient algorithm to put any given $g$ into the form $(X-a{)}^{k}h$ with $h(P)\ne 0,\mathrm{\infty }$, provided $P$ is not a point of order 2.

It turns out this definition can be extended to points of order 2, and also the point $O$ (when we homogenize the functions and work over the projective plane). Moreover, every rational function has as many zeroes as poles counting multiplicities, because of the way we extend the definition to the point at infinity.

TODO: link to page with proofs

Divisors

Divisors are a device for keeping track of poles and zeroes. For example, suppose a function $g$ has a zero at a point $P$ of order 3, and a pole at another point $Q$ of order 2, and a pole at $O$ of order 1. (Note the number of zeroes and poles are equal, as they must be.) Then using divisors, we can say all this concisely as follows:

We define these concepts more precisely.

The group of divisors is the free abelian group generated by the points of $E$ and is denoted $Div(E)$. (The angle brackets are present to avoid confusion between points of $E$ and elements of $Div(E)$, that is, to make it clear we are talking about zeroes and poles at points, not the points themselves.)

Let $\Delta ={\sum }_{P\in E}{m}_P⟨P⟩$ be a divisor. Then define its degree by $\mathrm{deg}\Delta ={\sum }_{P\in E}{m}_P$.

The subgroup of $Div(E)$ consisting of all divisors of degree zero is denoted ${Div}^0(E)$.

Let $g$ be a nonzero rational function. Then

where ${ord}_P(g)$ is the number of zeroes or poles at $P$ (and is negative if it represents the number of poles). Such a divisor is called principal, that is, a divisor is a principal divisor if it represents the zeroes and poles of some rational function. The group of principal divisors is denoted $Prin(E)$.

Since every rational function has as many zeroes as poles, we see that $Prin(E)$ is a subgroup of ${Div}^0(E)$.

Example

Suppose $P=(a,b)$ is a (finite) point. Let $g(X,Y)=X-a$. Then we have

(When $P$ has order 2, then $P=-P$ so this could be written as $⟨g⟩=2⟨P⟩-2⟨O⟩$.)

Consider a line $g=Y-(\mathrm{mX}+b)$ that is not vertical. It intersects the curve at three finite points $P,Q,R$. Then

Equivalent Divisors

An equivalence relation can be defined on the group of divisors as follows. We say that two divisors $D_1,D_2$ are linearly equivalent (written as $D_1~D_2$) if $D_1-D_2\in Prin(E)$.

In other words, there exists a rational function whose zeroes and poles are exactly the difference between the $D_1$ and $D_2$.

Pushing zeroes and poles to infinity

Theorem: Let $D\in Div(E)$. Then there exists a unique point $P\in E$ such that

Proof: (Existence:) We find lines with zeroes and poles in the right places to add and subtract from $D$.

Let $D={\sum }_{P\in E}{m}_P⟨P⟩$. For this proof, define the norm of the divisor $D$ to be

If $\mid D\mid =1$ then we are done as it is already in the desire form. Otherwise we show how to replace $D$ by another divisor with a smaller norm. There are several stages to the algorithm. Firstly:

-If there are two points +++$P,Q$+++ with +++$m_P,m_Q>0$+++,
subtract the divisor of the line +++$l$+++ through +++$P$+++ and +++$Q$+++.
Then +++$m_P,m_Q$+++ are both reduced by one.
+
If +++$P\ne -Q$+++ then the line +++$l$+++ also intersects +++$E$+++ at a
third finite point +++$R$+++, and in this case +++$m_R$+++ is increased by one.
+
Either way, the norm is reduced by at least one.
- If there are two points +++$P,Q$+++ with +++$m_P,m_Q<0$+++,
then add the line +++$l$+++ through +++$P$+++ and +++$Q$+++, and as above,
the norm is reduced by at least one.

By repeating the above, eventually we will have reduced $D$ to the form $m⟨P⟩-n⟨Q⟩+o⟨O⟩$. Then:

• If $m\ge 2$ then subtract the divisor of the tangent line at $P$, which reduces $m$ by 2 but also increases $m_R$ for some point $R$. This reduces the norm by at least one. If $n\ge 2$ then a similar procedure is performed on $Q$; we add the divisor of the tangent line at $Q$.

• If $m=n=1$ then we first add the line through $Q$ and $-Q$, which zeroes $m_Q$, but increases $m_{-Q}$. We are then left with the first case described in the previous stage, so we subtract the line through $P$ and $-Q$.

Hence eventually we find a divisor $D\prime ~D$ with $\mid D\prime \mid \le 1$. If $D\prime$ is still not in the desired form:

• If $\mid D\prime \mid =0$ then write $D\prime =⟨O⟩+(\mathrm{deg}D-1)⟨O⟩)$.

• If $D\prime =-⟨P⟩+(\mathrm{deg}D+1)⟨O⟩)$, then we add the divisor of the line through $P$ and $-P$ to get $⟨-P⟩+(\mathrm{deg}D-1)⟨O⟩$.

(Uniqueness:) suppose $D~⟨P⟩-o⟨O⟩~⟨Q⟩-o⟨O⟩$.

This implies $⟨P⟩-⟨Q⟩$ is principal, which is a contradiction unless $P=Q$ (for it would imply there exists a rational function with only one finite pole and only one finite zero).

The procedure used in the proof shows how to build a rational function corresponding to any given principal divisor. In brief: we start with the constant function 1 and the zero divisor and add/subtract divisors of lines to get to the target principal divisor. Every time we add the divisor of a line, we multiply our function by the equation of that line, and similarly, every time we subtract a divisor of a line, we divide the function by the equation of that line.

We shall see later how this is used in the computation of certain bilinear maps.

The sum map

Define the map $\mathrm{sum}:Div(E)\to E$ by

In other words, we treat the poles and zeroes as points on the elliptic curve and add and subtract them together according to their multiplicities.

Fact: Let $D=\sum m_P⟨P⟩$ be a divisor. Then $D$ is principal if and only if $\mathrm{deg}(D)=\sum m_P=0$ and $\mathrm{sum}(D)=\sum m_{P}P=O$.

The result about the degree of $D$ follows from the fact that rational functions have equal numbers of poles and zeroes.

The other result in the above fact is not hard to see: from the above proof, we can build a rational function with a given principal divisor by multiplying several equations of lines together. Each line $l$ goes through two or three finite points. If $l$ goes through two finite points, then one is the inverse of the other. If $l$ goes through three finite points, from the chord-tangent composition law, we have that the third point is exactly the inverse of the sum of the other two. Either way, $\mathrm{sum}(l)=0$.

The converse is similar. Starting with a divisor $D$ with $\mathrm{sum}(D)=O$, we build a rational function by multiplying lines together while reducing the norm of $D$. Eventually, $D$ is reduced to the zero divisor (it cannot be anything else, otherwise $\mathrm{sum}(D)\ne 0$), and the rational function we have constructed has divisor $D$, showing that $D$ is principal.

Fact: Rational functions with a given divisor are unique up to a constant.