4.2 Elliptic curve groups

Geometric group law

We want to define a group made of the points of elliptic curve. We will make two definitions - one is geometrical and the other is algebraic. We'll start with geometric.

Consider an elliptic curve in Weierstass form $E/F$ and recall that is has a point $O=[0,1,0]$.

First we will define the neutral element of the elliptic curve group to be $O$.

Next if we have a point $P=(x_0,y_0) \in E_F$ then we define the inverse $-P:=(x_0,-y_0)\in E_F$. Thus $P+(-P)=O$.

Finally if we have two points $P=(x_p,y_p), Q = (x_q,y_q) \in E_F$ and draw a line through this points (or tangent line if $P=Q$, remember we can always do it since the curve is smooth). If the line of the equation is $l:=ax+by+c$ and since $ax_p+by_p+c=0$ and $ax_q+by_q+c=0$ we know that $l \in F[x,y]$. So for other points of intersection we'll have the system of equations:

$$\begin{cases} ax+by+c=0 \\ y^2=x^3+Ax+B \end{cases}$$

This set of equations have at least two roots $P$ and $Q$ so since we have an equation of degree 3 it will have a 3rd point that we'll assign $-(P+Q)$ in a group. Note that if $b \ne 0$ then we'll have an equation in $F[x,y]$ (that is with coefficents from $F$, not $\overline F$). Then $x_p+x_q+x_{-(p+q)}$ will be the coefficent of polynomal at $x$ which is in $F$. So $x_p+x_q+x_{-(p+q)} \in F, x_p \in F, x_q \in F \implies x_{-(p+q)} \in F$. From $ax+by+c=0$ we also imply that $y_{-(p+q)} \in F$.

Thus we have the following three cases for adding points on elliptic curve:

1. $P \ne Q$

2. $P = Q$

3. $P = -Q$

Let's summarize the geometric group law. Consider a curve

$$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6 \\$$

If $P_0:=(x_0,y_0)$ then $-P_0=(x_0,-y_0-a_1x_0-a_3)$

Now consider points $P_1+P_2=P_3, P_i:=(x_i,y_i)$.

Case 1.

If $x_1=x_2, y_1+y_2+a_1x_2+a_3=0$ then $P_3=0$

Case 2.

We consider a line $y=ax+b$:

$$\begin{cases} a=\frac{y_2-y_1}{x_2-x_1}, b=\frac{y_1x_2-y_2x_1}{x_2-x_1} \text{ if } x_1 \ne x_2\\ a=\frac{3x_1^2+2a_2x_1+a_4-a_1y_1}{2y_1+a_1x_1+a_3}, b=\frac{-x_1^3+a_4x_1+2a_6-a_3y_1}{2y_1+a_1x_1+a_3} \end{cases}$$

Then we have:

$$x_3 = a^2+a_1a-a_2-x_1-x_2 \\ y_3 = -(a+a_1)x_3 - b - a_3 \\$$

Algebraic group law

As part of geometry - algebra duality that we saw several times earlier we want to define an algebraic group on elliptic curve and prove that it's isomorphic to the geometric group. This group will be a factor group

$$\text{Pic}^0(E):=\text{Div}^0(E)/\text{Div}_{\lang \rang}(E)$$

Next we're gonna make several propositions to prove that this group is isomorphic to the geometric group.

Proposition 4.2.1: Equivalent divisors on elliptic curve

$$\begin{align*} &\sphericalangle \\ &(E,O) \in \mathcal E \\ \hline \\ &(P) \sim (Q) \iff P=Q \end{align*}$$

Proof

$\implies$

$$(P) \sim (Q) \implies \exists f \in F(E): \text{div}(f)=(P)-(Q)$$

Next $(P)>0 \implies \text{div}(f) + (Q) >0 \implies f \in L((Q))$. But by $(3.4.14.c)$ we have

$$\dim L((Q))=1$$

So $f \in \overline F \implies (P)-(Q)=0 \implies (P)=(Q) \implies P = Q$.

$\impliedby$

Obvious

$\square$

Proposition 4.2.2: Divisor-to-point map

$$\begin{align*} &\sphericalangle \\ &(E,O) \in \mathcal E \\ &D \in \text{Div}^0(E) \\ \hline \\ &\exists! P \in E: D \sim (P)-(O) \end{align*}$$

Proof

Existence

Consider a divisor $D_O:=D+(O)$, it has $\deg D_O=\deg D+\deg O=1 > 2g-2$ so by $(3.4.14.c)$ we have:

$$\dim L(D+(O))=1$$

Consider some non zero $f \in L(D+(O))$. By definition of $L$ and $(3.4.11)$ we know that:

$$\text{div}(f) \ge -D-(O), \deg(\text{div}(f))=0$$

Since $-D-(O)$ gives a lower bound, we cannot have more poles than that. And this lower bound degee is $-1$ so there's exactly one point we can add to make $\deg(\text{div}(f))=0$. So

$$\text{div}(f) = -D-(O)+(P)$$

for some points $P \in E$. Hence

$$D \sim (P)-(O)$$

Uniqueness

Consider $D \sim (P')-(O)$, in this case:

$$(P')\sim (D)+(O) \sim (P)$$

So by $(4.2.1): P'=P$

$\square$

Note that $[D]_\sim$ is an element of $\text{Pic}^0(E)$ and $(4.2.2)$ tells us that each such class of equivalence has a unique corresponding point in $E$. That means we can define a map:

$$\varepsilon: \text{Pic}^0(E) \to E$$

Then

$$\varepsilon^{-1}:E \to \text{Pic}^0(E), P \to (P)-(O)+\text{Div}_{\lang \rang}(E)$$

Proposition 4.2.3: Algebraic-geometric group isomopshism

$$\begin{align*} &\sphericalangle \\ &(E,O) \in \mathcal E \\ \hline \\ &\begin{align*} &\varepsilon: \text{Pic}^0(E) \leftrightarrow E \hspace{0.5cm} \tag{a}\\ &\forall P, Q \in E: \varepsilon^{-1}(P+Q): = \varepsilon^{-1}(P)+\varepsilon^{-1}(Q) \hspace{0.5cm} \tag{b}\\ &\varepsilon: \text{Pic}^0(E) \cong_G E \hspace{0.5cm} \tag{c}\\ \end{align*} \end{align*}$$

Proof

a.

First note that $\varepsilon$ is surjective because $\varepsilon((P)-(O)+\text{Div}_{\lang \rang}(E))=P$.

Consider $D_1 + \text{Div}_{\lang \rang}(E), D_2 + \text{Div}_{\lang \rang}(E): \varepsilon(D_1 + \text{Div}_{\lang \rang}(E))=\varepsilon(D_2 + \text{Div}_{\lang \rang}(E)) = P$. It means that $D_1 \sim (P)-(O) \sim D_2$ so $D_1 + \text{Div}_{\lang \rang}(E)=D_2 + \text{Div}_{\lang \rang}(E)$

Thus we proved $\text{Pic}^0(E) \leftrightarrow E$, in particular $\varepsilon^{-1}$ is well-defined.

b.

Consider a projective line in $\mathbb P^2$ that goes through $P$ and $Q$:

$$l:ax+by+cz=0, b \ne 0 \\$$

Denote $R$ the third point of intersection. If point $P:=[x_0, y_0, 1]$ then we have $z(ax_0+bx_0+c)=0$ so we can equivalently write the line equation as

$$l: a(x-x_0z)+b(y-y_0z)=0$$

and we know from examples befor that $\mathfrak m_P=\lang \frac{y-y_0z}{z} \rang_I$. Then

$$\text{ord}_P(l/z)=\text{ord}_P(a(x-x_0z)/z+b(y-y_0z)/z)= \\ \text{ord}_P(\frac{b(y-y_0)}{z})+\text{ord}_P(1+a\frac{x-x_0}{y-y_0})=1$$

(note that like we saw in examples earlier that $\text{ord}_P(x-x_0)=2, \text{ord}_P(y-y_0)=1$)

The same will work for $Q$ and $R$.

Now the pole of $l/z$ (again refer to examples before):

$$\text{ord}_{O}(\frac{ax+by+cz}{z})=\text{ord}_{O}(\frac{ax+by+cz}{y})+\text{ord}_{O}(y/z)=-3$$

So we have:

$$\text{div}(l/z)=(P)+(Q)+(R)-3(O)$$

Now for the line $l'$ passing trough $P+Q$ and $R$:

$l':a'x+c'z=0$

Similar to the above we'll have two zeros of order one in $R$ and $P+Q$. But for $O$ we'll have $b=0$ so $\text{ord}_{O}(\frac{ax+cz}{y})=1$ and this the pole at $O$ has order $-2$. To sum up

$$\text{div}(l'/z)=(P+Q)+(R)-2(O)$$

So we have:

$$0\sim \text{div}(l'/l)=(P+Q)+(R)-2(O)-(P)-(Q)-(R)+3(O)=\\ (P+Q)-(P)-(Q)+(O) = ((P+Q)-(O))-((P)-(O))-((Q)-(O)) \implies \\ \varepsilon^{-1}(P+Q)=\varepsilon^{-1}(P)+\varepsilon^{-1}(Q)$$

c.

Follows immediately from $(a)$ and $(b)$

$\square$

def: Elliptic curve group multiplication by integer

$$\begin{align*} &\sphericalangle \\ &(E,O) \in \mathcal E \\ &P \in E \\ \hline \\ &[n]P:=\underbrace{P+P+\ldots+P}_{n \text{ times}} \end{align*}$$

note

This is standard thing that we already discussed that each group is a $\Z$-module

Proposition 4.2.4: Prinicipal divisor criterion

$$\begin{align*} &\sphericalangle \\ &(E,O) \in \mathcal E \\ &D = \sum_{P \in E}n_P(P) \\ \hline \\ &D \in \text{Div}_{\lang \rang}(E) \iff D \in \text{Div}^0(E), \sum_{P \in E}[n_P]P=O \end{align*}$$

Proof

$$D \in \text{Div}_{\lang \rang}(E) \iff D \sim 0 \iff O=\varepsilon^{-1}(D+\text{Div}_{\lang \rang}(E))=\\ \sum_{P \in E}[n_P](P-O)=\sum_{P \in E}[n_P]P$$

$\square$

Isogenies

def: Isogeny

$$\begin{align*} &\sphericalangle \\ &(E_1, O_1), (E_2, O_2) \in \mathcal E \\ & \phi: E_1 \rightsquigarrow_{Rsp} E_2 \\ & \phi(O_1)=\phi(O_2) \\ \hline \\ &\phi: E_1 \rightsquigarrow_{\mathcal E} E_2 \\ &\phi - \text{isogeny} \end{align*}$$

def: Multiplicaion-by-m isogeny

$$\begin{align*} &\sphericalangle \\ &(E, O) \in \mathcal E \\ &m \in \Z \\ &[m]: E \rightsquigarrow_{\mathcal E} E, \begin{cases} P \mapsto [m]P, m \ge 0 \\ P \mapsto [-m](-P), m<0 \end{cases} \\ \hline \\ &[m] -\text{multiplication by m isogeny} \end{align*}$$

Note that we just defined a group law but why is is an isogeny? We'll not give the proof here but the main idea is it clearly sends $O$ to $O$ and taking the formulas from the geometric group law it's clear that it's a rational map. Since $E$ is smooth (non-singular) then it's a morphism as well.

Propostion 4.2.4: Isogeny induces a group homomorphism

$$\begin{align*} &\sphericalangle \\ &(E_1, O_1), (E_2, O_2) \in \mathcal E \\ & \phi: E_1 \rightsquigarrow_{\mathcal E} E_2 \\ & P, Q \in E_1 \\ \hline \\ &\phi: (E_1, O_1) \rightsquigarrow_G (E_2, O_2) \end{align*}$$

Proof

If $\forall P \in E_1: \phi(P)=0$ then there's nothing to prove. Otherwise $\phi \ne \text{const}$ and notice that by $(3.4.10)$ $\phi^*$ and $\phi_*$ takes divisors of degree $0$ to divisors of degree $0$ and principal divisors to principal divisors. Moreover they do it as homomorphisms:

$$\phi^*: \text{Pic}^0(E_2) \rightsquigarrow_G \text{Pic}^0(E_1) \\ \phi_*: \text{Pic}^0(E_1) \rightsquigarrow_G \text{Pic}^0(E_2) \\$$

Coupling that with $(4.2.3)$ we have the commutative diagram:

$$\begin{CD} E_1 @>\cong, \varepsilon_1^{-1}>> \text{Pic}^0(E_1) \\ @V\phi VV @VV\phi_*V \\ E_2 @<\cong, \varepsilon_2<< \text{Pic}^0(E_2) \end{CD}$$

Thus $\phi$ is a homomorphism

$\square$

In the course of the proof we shown $\phi$ as a group homomorphism using zero degree-zero picard groups. But we can also go in other direction and build a $E_2 \rightsquigarrow_G E_1$ homomorphism using $\phi^*$:

$$\begin{CD} E_1 @<\cong, \varepsilon_1<< \text{Pic}^0(E_1) \\ @A\hat \phi AA @AA\phi^*A \\ E_2 @>\cong, \varepsilon_2^{-1}>> \text{Pic}^0(E_2) \end{CD}$$

Proposition 4.2.6: Dual isogeny

$$\begin{align*} &\sphericalangle \\ &(E_1, O_1), (E_2, O_2) \in \mathcal E \\ & \phi: E_1 \rightsquigarrow_{\mathcal E} E_2, \phi \ne \text{const} \\ &\deg \phi = m \\ \hline \\ &\exists! \hat \phi: (E_2, O_2) \rightsquigarrow_{\varepsilon_E} (E_1, O_1), \phi \circ \hat \phi = [m] \\ &\text{Then as a group homomorphism}:\\ &\begin{align*} &\hat \phi: (E_2, O_2) \rightsquigarrow_G \text{Div}^0 (E_2) \overset{\phi^*}\rightsquigarrow_G \text{Div}^0 (E_1) \overset{\text{sum}} \rightsquigarrow_G (E_1, O_1) \\ &\hat \phi: Q \mapsto (Q) - (O) \mapsto \phi^*((Q)-(O))=\sum n_P(P) \mapsto \sum [n_P]P\\ \end{align*} \end{align*}$$

def: Dual isogeny

$$\begin{align*} &\sphericalangle \\ &(E_1, O_1), (E_2, O_2) \in \mathcal E \\ & \phi: E_1 \rightsquigarrow_{\mathcal E} E_2 \\ \hline \\ &\hat \phi - \text{dual isogeny from } (4.2.6) \\ &\phi = \text{const} \implies \phi=\hat \phi = [0] \end{align*}$$

Proposition 4.2.6: Dual isogeny properties

$$\begin{align*} &\sphericalangle \\ &(E_1, O_1), (E_2, O_2) \in \mathcal E \\ & \phi: E_1 \rightsquigarrow_{\mathcal E} E_2, \phi \ne \text{const} \\ &\deg \phi = m \\ \hline \\ &\begin{align*} &\phi \circ \hat \phi = [m] \text{ on } E_1, \hat \phi \circ \phi = [m] \text{ on } E_2\hspace{0.5cm} \tag{a}\\ &\eta: E_2 \rightsquigarrow_{\mathcal E} E_3 \implies \widehat{\phi \circ \eta} = \hat \phi \circ \hat \eta \hspace{0.5cm} \tag{b}\\ &\psi: E_1 \rightsquigarrow_{\mathcal E} E_2 \implies \widehat{\phi + \psi} = \hat \phi + \hat \eta \hspace{0.5cm} \tag{c}\\ &\forall n \in \Z: \widehat{[n]}=[n]\hspace{0.5cm} \tag{d}\\ &\deg \phi = \deg \hat \phi \hspace{0.5cm} \tag{e}\\ &\hat {\hat \phi}=\phi\hspace{0.5cm} \tag{f}\\ \end{align*} \end{align*}$$

Proposition 4.2.7: Multiplicaion-by-m isogeny degree

$$\begin{align*} &\sphericalangle \\ &(E, O) \in \mathcal E \\ & m \in \Z \\ \hline \\ &\deg[m]=m^2 \end{align*}$$

Proof

Let $d=\deg[m]$ and consider $\phi=[m]$. Then by $(4.2.6)$:

$$[d]=\phi \circ \hat \phi = [m]\circ \widehat{[m]}=[m]\circ[m]=[m^2] \implies d = m^2$$

$\square$

def: Positive definite quadratic form

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G^{\mathcal A} \\ &d: G \to \R \\ &(.\,,.): G \times G \to \R, (a, b) \mapsto d(a+b) - d(a) - d(b) \\ &\forall a_1, a_2, b \in G: (a_1+a_2, b) =(a_1, b) + (a_2, b) \\ &\forall a, b_1, b_2 \in G: (a, b_1+b_2) =(a, b_1) + (a, b_2) \\ &\forall a \in G: d(a) \ge 0 \\ &d(a) = 0 \iff a = e\, (\text{neutral element}) \\ \hline \\ &d - \text{positive definite quadratic form} \end{align*}$$

For elliptic curves we define $\text{Hom}(E_1, E_2)$ as the set of all isogenies from $E_1$ to $E_2$.

Proposition 4.2.8: Isogenies degree is a positive definite quadratic form

$$\begin{align*} &\sphericalangle \\ &(E_1, O_1), (E_2, O_2) \in \mathcal E \\ &\text{deg}: \text{Hom}(E_1, E_2) \to \Z, \phi \mapsto \deg \phi \\ \hline \\ &\text{deg } - \text{positive definite quadratic form} \end{align*}$$

Elliptic curve group over a finite field

Consider and elliptic curve defined over $\mathbb F_q: (E,O)/\mathbb F_q$. Obviously

$$|E_{\mathbb F_q}| \le q^2$$

We can easily refine it further since for each $x$ in the equation we get a maximum of two $y$ so the trivial upper bound is:

$$|E_{\mathbb F_q}| \le 2q+1$$

Let's make it even more precise.

Proposition 4.2.9: Separability of multiplication-by-m and Frobenuis in a finite field

$$\begin{align*} &\sphericalangle \\ &q=p^n, p \in \mathfrak P \\ &(E, O)/\mathbb F_q \in \mathcal E \\ \hline \\ &m+n\rho_{\rightsquigarrow}^n - \text{ separable} \iff p \nmid m \end{align*}$$

Before going further we note the following fact. Each field extension $E/F$ may be decomposed into $E/_{\boxminus}S/_{\Box}F$ and so we can define the degree of a rational map $\deg \phi = \deg \phi_s \cdot \deg \phi_i$. Where $\deg \phi_s$ is the degree of separable extension and $\deg \phi_i$ is the degree of purely inseparable extension.

Now remember that separability is a notion of whether all roots are different (separable) or all roots are glued into one (purely inseparable). In case of ramification we have several points in pre-image glued together into one. This hints that there's a relation between separability and ramification. In general it is true that unramified mapping is necessary separable. Moreover in case of elliptic curves:

$$\forall Q: \\ \#\phi^{-1}(Q)= \deg \phi_s \\ e_\phi(Q) = \deg \phi_i \\$$

The above discussions needs strict proofs but we'll skip it here for brevity.

Propostion 4.2.10: Number of points in kernel is separable mapping degree

$$\begin{align*} &\sphericalangle \\ &(E_1, O_1), (E_2, O_2) \in \mathcal E \\ & \phi: E_1 \rightsquigarrow_{\mathcal E} E_2 \\ & \phi - \text{separable} \\ \hline \\ &|\ker{\phi}|=\deg \phi \end{align*}$$

Proof

By definition $|\ker \phi| = |\phi^{-1}(O)| = \deg \phi$ since $\phi$ is separable.

$\square$.

Proposition 4.2.11: Hasse bound

$$\begin{align*} &\sphericalangle \\ &q = p^n, p \in \mathfrak P \\ &(E, O) / \mathbb F_q \in \mathcal E \\ \hline \\ &q+1-2\sqrt q \le |E_{\mathbb F_q}| \le q+1+2\sqrt q \end{align*}$$

Proof

First consider some quadratic form $d$ with $(a,b):=d(a+b)-d(a)-d(b)$ and assume it has values in $\Z$. Then we have:

$$(e,e) = (e+e,e)=(e,e)+(e,e) \implies (e,e)=0 \\ 0 = (e,e)=d(e+e)-2d(e)=-d(e) \implies d(e)=0 \\ (a,e)=d(a+e)-d(a)-d(e)=0 \\ 0=((m-1)a, a-a)=((m-1)a, a)+((m-1)a, -a)= \\ d(ma)-d((m-1)a)-d(a)+d((m-2)a)-d((m-1)a)-d(a)= \\ d(ma)-2d((m-1)a)+d((m-2)a)-2d(a) \implies \\ d(ma)= 2d((m-1)a)+2d(a)-d((m-2)a)$$

We want to prove that $d(ma)=m^2d(a)$. Obvoiusly true for $m=1$. Assume it's true for $n\le m-1$:

$$d(ma)=2(m-1)^2d(a)+2d(a)-(m-2)^2d(a)=m^2d(a)$$

Next:

$$0 \le d(ma-nb)=(ma,nb)+d(ma)+d(nb)=mn(a,b)+m^2d(a)+n^2d(b)$$

Assume $m:=-(a,b), n:=2d(a)$ then

$$-2d(a)(a,b)^2+(a,b)^2d(a)+4d(a)^2d(b) = d(a)(4d(a)d(b)-(a,b)^2) \ge 0 \implies \\ 4d(a)d(b)-(a,b)^2 \ge 0 \implies \\ |(a,b)| \le 2\sqrt{d(a)d(b)}$$

In particluar, using $(4.2.8)$:

$$|\deg(\phi+\psi)-\deg(\phi)-\deg(\psi)| \le 2 \sqrt{\deg(\phi)\deg(\psi)}$$

Next, consider $E_{\mathbb F_q}$. We know that $E_{\mathbb F_q}=\{P \in E: \forall \sigma \in \text{Gal}(\overline {\mathbb F}_q/\mathbb F_q): P^{\sigma}=P\}$. From $(2.10.5)$ we know that $\text{Gal}(\mathbb F_q/ \mathbb F_p) = \lang \rho \rang$. By $(2.8.10)$ any extension $\mathbb F_r$ of $\mathbb F_q$ will have the property $r=q^k$ for some $k$. Thus $\text{Gal}(\mathbb F_r/ \mathbb F_q)=\lang \rho^n \rang$. Since $\overline F$ is the limit fo such extensions and each Galois group is generated by $\rho^n$ then $\text{Gal}(\overline{\mathbb F}_q/ \mathbb F_q)=\lang \rho^n \rang$. And so we can say that

$$E_{\mathbb F_q}=\{P \in E: P^{\rho^n}=P\}$$

By $(4.2.9)$ we know that $(1-\rho^n)$ is a separable mapping so by $(4.2.10)$ we have:

$$|E_{\mathbb F_q}|=|\ker (1-\rho^n)|=\deg(1-\rho^n)$$

Finally recall that by $(3.4.8.c): \deg\rho^n=p^n=q$ and obviously $\deg[1]=1$ so:

$$||E_{\mathbb F_q}|-q-1|=|\deg(1-\rho^n)-\deg(\rho^n)-\deg[1]|\leq 2\sqrt{\deg(\rho^n)\deg[1]}=2\sqrt q$$

$\square$