4.3 Pairings

Torsion subgroups

def: m-torsion subgroup

$$\begin{align*} &\sphericalangle \\ &(E, O) \in \mathcal E \\ &m \in \N \\ \hline \\ &E[m]:=\{P \in E: [m]P=0\} \end{align*}$$

note

The $m$-torsion is essentially the elements of order $m$ and order $d$ if $d \mid m$.

In fact it's exactly the same as $\ker [m]$,

def: Torsion subgroup

$$\begin{align*} &\sphericalangle \\ &(E, O) \in \mathcal E \\ \hline \\ &E_{\text{tors}}:=\bigcup_{m \in \N} E[m] \end{align*}$$

Proposition 4.3.2: m-torsion structure

$$\begin{align*} &\sphericalangle \\ &p = \text{char } F \\ &(E, O)/F \in \mathcal E \\ &p \nmid m (\text{including } p=0) \\ \hline \\ &E[m]\cong \Z/m\Z \times \Z/m\Z \end{align*}$$

Proof

By $(4.2.9)$ $[m]$ is separable so by $(4.2.7)$ and $(4.2.10)$:

$$m^2=\deg[m]=|\ker [m]|\equiv|E[m]|$$

Note that for every $d \mid m$ we also have $|E[d]|=d^2$ so by $(2.2.39)$ we have:

$$E[m]\cong \Z/m\Z \times \Z/m\Z$$

$\square$

note

Though $(E,O)$ is defined over $F$ it still has points in $\overline{F}$ and so does $E[m]$. It might be surprising that that we can grow $m$ and get arbitrary large order of $E[m]$ given that we count points of $E_{\mathbb F_q}$ in $(4.2.11)$. But again we're considering points in $E=E_{\overline{\mathbb F}}$ and this group has infinite number of points since $\overline {\mathbb F}$ is infinite.

Now assume $m$ is prime and we'll rename it to $r$ to signify that its primeness. So we have $E[r]\cong \Z/r\Z \times \Z/r\Z$. In this case the only non-trivial subgroups would have order $r$ since only $r \mid r^2$. Note that each $\Z/r\Z$ is cyclic in this case any element will generate the whole group. Moreover, the same is true for any subgroup of order $r$ in $E[r]$. We'll have the following $r+1$ subgroups of order $r$:

$$\lang (0,1) \rang_G \\ \lang (1,0) \rang_G \\ \lang (1,1) \rang_G \\ \lang (1,2) \rang_G \\ \ldots \\ \lang (1,r-1) \rang_G \\$$

Why is this list exaustive and each group is unique? Because if we take any element $(a, b)$ then if $a =0$, the element is a part of $\lang (0,1) \rang_G$, if $b=0$ it will be a part of $\lang (1,0) \rang_G$. In all other cases this element would be a part of one and exactly of the last $r-1$ groups.

Note that $(0,0)$ is part of every group, other than that each element is unique to its own group. We can cross-check it by counting orders $r(r+1)-r=r^2$ ($-r$ for removing $(0,0)$ duplicates). This gives the following visualization for subgroups of order $r$ in $r$-torsion:

Of course we use here integers but on elliptic curve this will be elliptic curve points.

Propostion 4.3.1: Weil conjectures for elliptic curves

$$\begin{align*} &\sphericalangle \\ &q=p^n, p \in \mathfrak P \\ &(E,O)/\mathbb F_q \in \mathcal E \\ &t:= |E_{\mathbb F_q}|-q-1 \\ &\chi(x):=x^2-tx+q \\ & \alpha, \beta: \chi(\alpha)=\chi(\beta)=0 \\ & \phi:=\rho_{\rightsquigarrow}^n \\ \hline \\ &\begin{align*} &|\alpha|=|\beta|=\sqrt q \hspace{0.5cm} \tag{a}\\ &|E_{\mathbb F_{q^k}}|=q^k+1-\alpha^k-\beta^k \hspace{0.5cm} \tag{b}\\ &\phi^2 - [t]\circ \phi + [q] = [0] \hspace{0.5cm} \tag{c}\\ \end{align*} \end{align*}$$

Note that we have two eigenvalues of Frobenius. The first one is $1$ because if we assume $\phi(P)=P$ then

$$\phi^2 - [t]\circ \phi + [q]=[1] - [t] + [q] = [1-t+q]=[E_{\mathbb F_q}]=[0]$$

Since the product of roots of characteriscic polynomial is $q$, the second root is $q$.

So when we have $r \mid q^k-1$ we have a torsion subgroup of size $r$ over $\mathbb F_q$. This will be part of the eigenspace of Frobenius with eigenvalue 1.

Consider a trace mapping:

$$T(P):=\sum_{\sigma \in \text{Gal}(\mathbb F_{q^k}/\mathbb F_{q})}\sigma(P)=\sum_{t=0}^{k-1}(x^{q^i},y^{q^i})$$

Note that it will fix $\mathbb F_q$ since the any Galois action will just permute the summands. Thus $\text{T}: \mathbb F_{q^k} \to \mathbb F_q$, in particular it sends the whole torsion to $E[r]_{\mathbb F_q}$ subgroup. We will call this subgroup a trace-image subgroup. Note that trace will fix each point of the trace-image subgroup, that is will send it to itself.

Now let's define another group by using and anti-trace map

$$T^a(P):=[k]P-T(P)$$

If we consider it as the map of the whole torsion then it will be a subgroup of this torsion because $T^a(P_1+P_2):=[k](P_1+P_2)-T(P_1+P_2)$. But we know that if there's a point $P$ in torsion that is outside of $\mathbb F_q$ then $[k]P$ is also outside, so this subgroup will be not empty and different from trace-image subgroup. Also note that

$$T(T^a(P))=T^a(P)+\phi(T^a(P))+\ldots + \phi^{k-1}(T^a(P))= \\ [k]P-T^a(P) + [k]\phi(P)-T(P)+\ldots + [k]\phi^{k-1}(P)-T(P) = \\ [k]T^a(P)-[k]T^a(P)=O$$

So we call this group a trace-kernel subgroup. As we noted above this group is not empty so the kernel is at least the size of this group which is $r$. But kernel cannot be the whole torsion because the trace-image group is not empty. So the trace-kernel subgroup is exactly the kernel of the trace map.

Finally if there's a point $P\in E[r]: \phi(P)=[q]P$ then $T(P)=P+[q]P+\ldots+[q^{k-1}]P=[(q^k-1)/(q-1)]P=O$. So we can say that trace-kernel subgroup is the intersection of torsion an the eigenspace of Frobenius with eigenvalue $q$.

To sum up we have two groups:

$$\begin{array}{c|c|c} \mathbb G_1: = T(E[r]) & \text{trace-image subgroup} & \phi(P)=P \\ \mathbb G_2 := \ker_{E[r]} T & \text{trace-kernel subgroup} & \phi(P)=[q]P \\ \end{array}$$

Weil pairing

We want to have a pairing function that maps two points of elliptic curve to a field that is bilinear, non-trivial and Galois invariant.

Consider a field $F$ with $\text{char} F=p$, $m: p \nmid m$ and a point $Q \in E[m]$. Then since $[m]Q-[m]O=O$ by $(4.2.4)$ there's a function $f_{m,Q} \in F(E)$:

$$\text{div}(f_{m, Q})=m(Q)-m(O)$$

Since $[m]\ne \text{const}$ and it's a morphism then by $(3.4.5)$ it's surjective so we can find a point

$$Q_{[m]^{-1}}:[m]Q_{[m]^{-1}}=Q$$

Consider a divisor:

$$D:=[m]^*(Q)-[m]^*(O)=\sum_{S \in [m]^{-1}(Q)}e_{[m]}(S)(S)-\sum_{T \in [m]^{-1}(O)}e_{[m]}(T)(T)$$

Recall that by $(4.2.9)$ $[m]$ is separable so it's unramified and $e_{[m]}=1$. Then note that preimage of $(O)$ is $\ker [m] \equiv E[m]$. And preimage of $Q$ is $Q_{[m]^{-1}}+E[m]$ so we have:

$$D= \sum_{R \in E[m]}(Q_{[m]^{-1}}+R)-(R)$$

Note that the degree of this divisor is obvoisly $0$ and $\sum_{R \in E[m]}Q_{[m]^{-1}}+R-R=\sum_{R \in E[m]}Q_{[m]^{-1}}=[m^2]Q_{[m]^{-1}}=[m]Q=O$, so $D$ is principal and there's a function $g_{m,Q}$:

$$\text{div}(g_{m,Q})=[m]^*(Q)-[m]^*(O)=\sum_{R \in E[m]}(Q_{[m]^{-1}}+R)-(R)$$

Then notice that:

$$(f_{m, Q} \circ [m])(P) = f_{m, Q}([m]P) \\ \text{div}(f_{m, Q} \circ [m]) = m\sum_{T \in [m]^{-1}(Q)}(T)-m\sum_{S \in [m]^{-1}(O)}(S)= \\ \sum_{R \in E[m]}m(Q_{[m]^{-1}}+R)-m(R) \\ \text{div}(g_{m, Q}^m) = \sum_{R \in E[m]}m(Q_{[m]^{-1}}+R)-m(R) = \text{div}(f_{m, Q} \circ [m]) \implies \\ \text{div}(\frac{g_{m, Q}^m}{f \circ [m]})=0 \implies f_{m, Q} \circ [m] = c g_{m, Q}^m$$

Since $g^m$ is derived from divisor and thus defined up to a constant we can assume $c = 1$ and so:

$$f_{m, Q} \circ [m] = g_{m, Q}^m$$

Next take some point $P \in E[m]$ and any point $X \in E$ then

$$(\frac{g_{m, Q}(X+P)}{g_{m, Q}(X)})^m=\frac{f_{m, Q}([m]X+[m]P)}{f_{m, Q}([m]X)}=1$$

So the mapping $\phi: E \to \mathbb P^1, X \mapsto \frac{g_{m, Q}(X+P)}{g_{m, Q}(X)}$ take finite number of values in $\overline F$ so it's not surjective and thus by $(3.4.5)$ it's consant. Moreover that value of $\phi$ is an $m$-th root of unity.

We'll denote the cyclic group of $m$-th roots of unity as $\mu_m:=\{x \in \overline F: x^m=1\}$.

def: Weil pairing

$$\begin{align*} &\sphericalangle \\ &(E, O)/F \in \mathcal E \\ &\text{char} F \nmid m \\ \hline \\ &e_m(P,Q): E[m] \times E[m] \to \mu_m, P,Q \mapsto \frac{g_{m, Q}(X+P)}{g_{m, Q}(X)} \end{align*}$$

Proposition 4.3.3: Weil pairing properties

$$\begin{align*} &\sphericalangle \\ &(E, O)/F \in \mathcal E \\ &\text{char} F \nmid m \\ &P_i, Q_i \in E[m] \\ \hline \\ &\begin{align*} &e_m(P_1+P_2,Q)=e_m(P_1,Q)e_m(P_2,Q) \hspace{0.5cm} \tag{a}\\ &e_m(P,Q_1+Q_2)=e_m(P,Q_1)e_m(P,Q_2) \hspace{0.5cm} \tag{b}\\ &e_m(P,P)=1 \hspace{0.5cm} \tag{c}\\ &e_m(P,Q)=e_m(Q,P)^{-1} \hspace{0.5cm} \tag{d}\\ &\forall \sigma \in \text{Gal}_{\overline F/F}: e_m(P,Q)^\sigma = e_m(P^\sigma ,Q^\sigma )\hspace{0.5cm} \tag{e}\\ &\forall P \in E[mm'], Q \in E[m]: e_{mm'}(P ,Q)=e_{m}([m']P ,Q) \hspace{0.5cm} \tag{f}\\ & (\forall S \in E[m]: e_m(S,T)=1) \implies T = O\hspace{0.5cm} \tag{g}\\ \end{align*} \end{align*}$$

Proof

a.

$$e_m(P_1+P_2, Q)=\frac{g_{m, Q}(X+P_1+P_2)}{g_{m, Q}(X)}= \\\frac{g_{m, Q}(X+P_1+P_2)}{g_{m, Q}(X+P_1)}\frac{g_{m, Q}(X+P_1)}{g_{m, Q}(X)} = e(P_1,Q)e(P_2,Q)$$

b.

Consider a function $h$ with divisor:

$$\text{div}(h)=(Q_1+Q_2)-(Q_1)-(Q_2)+(O)$$

Then we have

$$\text{div}(\frac{f_{m, Q_1+Q_2}}{f_{m, Q_1}f_{m, Q_2}})=m(Q_1+Q_2)-m(O)-m(Q_1)+m(O)-m(Q_2)+m(O) =\\ m(Q_1+Q_2)-m(Q_1)-m(Q_2)+m(O)=m\text{div}(h)=\text{div}(h^m) \implies \\ f_{m, Q_1+Q_2}=cf_{m, Q_1}f_{m, Q_2}h^m$$

Now let's compose it with $[m]$:

$$g^m_{m, Q_1+Q_2}=f_{m, Q_1+Q_2} \circ m=c(f_{m, Q_1} \circ m)(f_{m, Q_2} \circ m)(h^m \circ m) = \\ cg^m_{m, Q_1}g_{m, Q_2}^m(h^m \circ m) \implies \\ g_{m, Q_1+Q_2}=cg_{m, Q_1}g_{m, Q_2}(h \circ m)$$

So

$$e_m(P,Q_1+Q_2)=\frac{g_{m, Q_1+Q_2}(X+P)}{g_{m, Q_1+Q_2}(X)}=\\ \frac{g_{m, Q_1}(X+P)g_{m, Q_2}(X+P)h([m]X+[m]P)}{g_{m, Q_1}(X)g_{m, Q_2}(X)h([m]X)}=e_m(P,Q_1)e_m(P,Q_2)$$

c.

Consider a translation-by-P map $\tau_P: E \to E, Q \mapsto Q+P$. Then

$$\text{div}(\prod_{k=0}^{m-1}f_{m,P} \circ \tau_{[k]P}) = m\sum_{k=0}^{m-1}([1-i]P)-([-i]P)=0$$

So we have:

$$\forall X \in E: \prod_{k=0}^{m-1}(f_{m,P} \circ \tau_{[k]P})(X)=\text{const}$$

Now taking $P_{[m]^{-1}}:[m]P_{[m]^{-1}}=P$ we have:

$$(f_{m,P} \circ [m] \circ \tau_{[k]P_{[m]^{-1}}})(X)=f_{m,P}([m](X+[k]P_{[m]^{-1}}))= \\ f_{m,P}([m]X+[k]P) \\ \forall X \in E: \prod_{k=0}^{m-1}(g_{m,P}^m \circ \tau_{P_{[m]^{-1}}})(X) = \prod_{k=0}^{m-1}(f_{m,P} \circ [m] \circ \tau_{[k]P_{[m]^{-1}}})(X) =\\ \prod_{k=0}^{m-1}f_{m,P}([m]X+[k]P)$$

So it follows that:

$$\prod_{k=0}^{m-1}g_{m,P}^m \circ \tau_{P_{[m]^{-1}}} = \text{const} \implies \\ \prod_{k=0}^{m-1}g_{m,P} \circ \tau_{P_{[m]^{-1}}}= \text{const}$$

In particular taking $X' = X+P_{[m]^{-1}}$ so

$$\prod_{k=0}^{m-1}g_{m,P}(X+[k]P_{[m]^{-1}})=\prod_{k=0}^{m-1}g_{m,P}(X+[k+1]P_{[m]^{-1}})$$

Cancelling similar terms:

$$g_{m,P}(X)=g_{m,P}(X+[m]P_{[m]^{-1}})=g_{m,P}(X+P) \implies \\ e_m(P,P)=1$$

d.

$$e_m(P+Q,P+Q)=e_m(P,P)e_m(P,Q)e_m(Q,P)e_m(Q,Q) \implies \\ e_m(P,Q)e_m(Q,P)=1$$

e.

Recall that for any $f \in F(E), P \in E: f(P)^\sigma = f^{\sigma}(P^\sigma)$. Then

$$\text{div}(f_{m, Q})=m(Q)-m(O) \\ \text{div}(f^\sigma_{m,Q})=\text{div}(f_{m,Q})^\sigma=m(Q^\sigma)-m(O)=\text{div}(f_{m,Q^\sigma}) \implies \\ f^\sigma_{m,Q} = f_{m,Q^\sigma}$$

The same is true for $g$, so:

$$e_m(P,Q)^\sigma=\frac{g_{m, Q}^{\sigma}(X^{\sigma}+P^{\sigma})}{g^{\sigma}_{m, Q}(X^{\sigma})}= \frac{g_{m, Q^{\sigma}}(X^{\sigma}+P^{\sigma})}{g_{m, Q^{\sigma}}(X^{\sigma})}=e_m(P^\sigma, Q^\sigma)$$

f.

Notice that:

$$\text{div}(f_{m, Q}^{m'})=m'm(Q)-m'm(O) \\ (g_{m, Q}\circ [m'])^{mm'}=(f_{m, Q}\circ [mm'])^{m'}=f_{mm',Q}\circ [mm']=g_{mm',Q}$$

So

$$e_{mm'}(P,Q)=\frac{g_{m, Q}\circ [m'](X+P)}{g_{m, Q}\circ [m'](X)}=\frac{g_{m, Q}(Y+[m']P)}{g_{m, Q}(Y)}=e_{m}([m']P,Q)$$

g.

We will not prove it here.

$\square$

This definition of pairing works fine but it's a bit tedious for real world calculation. After all it involved finding $f$ with divisor $m(Q)-m(O)$ and $g$ with divisor $[m]^*(Q)-[m]^*(O)$ and then relate those two functions. We want to narrow it down to at least finding functions with $m(Q)-m(O)$.

We start this journey by defining how to calculate function of divisor.

def: Divisor support

$$\begin{align*} &\sphericalangle \\ &D = \sum n_P(P) \\ \hline \\ &\text{supp}(D):=\{P: n_P \ne 0\} \end{align*}$$

def: Divisor sum

$$\begin{align*} &\sphericalangle \\ &D = \sum n_P(P) \\ \hline \\ &\text{sum}(D):=\sum [n_P]P \end{align*}$$

def: Function evaluation on divisor

$$\begin{align*} &\sphericalangle \\ &(E, O) \in \mathcal E \\ &D = \sum n_P(P) \\ &f \in F(E) \\ &\text{supp}(\text{div}(f)) \cap \text{supp}(D) = \empty \\ \hline \\ &f(D):=\prod_{P \in \text{supp}(D)} f(P)^{n_P} \end{align*}$$

Note that this definition make sense if supports are disjoint. Otherwise we'll have $0$ on common point which will bring the whole evaluation to $0$.

Proposition 4.3.4: Weil reciprocity

$$\begin{align*} &\sphericalangle \\ &(E, O) \in \mathcal E \\ &f,g \in F(E) \\ &\text{supp}(\text{div}(f)) \cap \text{supp}(\text{div}(g)) = \empty \\ \hline \\ &g(\text{div}(f))=f(\text{div}(g)) \end{align*}$$

Proof

First, let's prove for the case $E = \mathbb P^1$. Consider two polynomials $f = (x-\alpha_1)\ldots(x-\alpha_n), g=(x-\beta_1)\ldots(x-\beta_k)$, where roots might be repeating. Then consider a following table:

$$\begin{matrix} \alpha_1-\beta_1 & \ldots & \alpha_n-\beta_k \\ \ldots \\ \alpha_n-\beta_1 & \ldots & \alpha_n-\beta_k \end{matrix}$$

Notice that $g(\text{div}(f))$ and $f(\text{div}(g))$ is the product of all terms in the table above ($g(\text{div}(f))$ goes by rows and $f(\text{div}(g))$ goes by columns). It is true only each term differs by $-1$ factor, so we get an "error" by $(-1)^{mk}$. But remeber that we're in a projective space so $f$ will have $n$ poles (or rather the pole of order $n$) and $g$ will have $k$ poles. We'll have the same mismatch $(-1)^{mk}$ there so the errors will cancel.

Now let's prove for arbitrary $E$. It can be proved that

$$f(\phi^*D)=(\phi_*f)(D), f(\phi_*D)=(\phi^*f)(D)$$

Consider a mapping:

$$\phi(P) = \begin{cases} [g(P), 1], g \in \mathcal O^r_{C,P} \\ [1,0], g \notin \mathcal O^r_{C,P} \end{cases}$$

Then

$$f(\text{div}(g))=f(\phi^*((0)-(\infty)))=(\phi_*f)((0)-(\infty))= \\ (\phi_*f)(\text{div}(x))$$

Now notice that the latter are actually functions in $\mathbb P^1$ so

$$f(\text{div}(g))=(\phi_*f)(\text{div}(x))=x(\text{div}(\phi_*f))=x(\phi_*\text{div}(f))= \\ \phi^*x(\text{div}(f))=g(\text{div}(f))$$

$\square$

def: Alternative definition of Weil pairing

$$\begin{align*} &\sphericalangle \\ &(E, O) \in \mathcal E \\ &m \in \N: \text{char}F \nmid m \\ &S, T \in E[m] \\ &D_S, D_T \in \text{Div}^0(E) \\ &\text{sum}(D_S)=S,\text{sum}(D_T)=T \\ &\text{supp}(D_S) \cap \text{supp}(D_T) = \empty \\ &h_S, h_T \in F(E):\text{div}(h_S)=mD_S, \text{div}(h_T)=mD_T \\ \hline \\ &\hat e_m(S,T):=\frac{h_T(D_S)}{h_S(D_T)} \end{align*}$$

Next we want to prove a serios of propositions that will lead us to the conclusion that this definition is equivalent.

From now on we'll assume that we always work in a torsion of the size $m$ so instead of writing $f_{m,P}$ we'll just write $f_P$.

First define two quantities:

$$c([m]V,[m]W):=\frac{f_{[m]V+[m]W}(X)}{f_{[m]V}(X)f_{[m]W}(X-[m]V)} \\ d(V,W):=\frac{g_{[m]V+[m]W}(X)}{g_{[m]V}(X)g_{[m]W}(X-V)} \\$$

Proposition 4.3.5: The alternative definition of Weil pairing

$$\begin{align*} &\sphericalangle \\ &(E, O) \in \mathcal E \\ &m \in \N: \text{char}F \nmid m \\ &S, T \in E[m] \\ \hline \\ &\begin{align*} & c([m]V,[m]W), d(V,W) = \text{const}(X)\hspace{0.5cm} \tag{a}\\ & d(V,W)^m=c([m]V,[m]W)\hspace{0.5cm} \tag{b}\\ & V,W,U \in E[m^2] \implies d(V,W+[m]U)=d(V,W)\hspace{0.5cm} \tag{c}\\ & V,W,U \in E[m^2] \implies d(V+[m]U,W)=d(V,W)e_m([m]U,[m]W)\hspace{0.5cm} \tag{d}\\ & \frac{d(U,V)}{d(V,U)}=\frac{d(V,W)d(U+W,V)}{d(V,U+W)d(W,V)}\hspace{0.5cm} \tag{e}\\ & e_m(S,T)=\frac{c(S,T)}{c(T,S)}\hspace{0.5cm} \tag{f}\\ & \hat e_m(S,T)=e_m(S,T)\hspace{0.5cm} \tag{g}\\ \end{align*} \end{align*}$$

Proof

a.

First note that

$$d(V,W)(X)^m=\frac{f_{[m]V+[m]W}([m]X)}{f_{[m]V}([m]X)f_{[m]W}([m]X-[m]V)}= \\ c([m]W,[m]V)([m]X)$$

So we have:

$$\text{div}(c(mV,mW))= \\ m([m]V+[m]W)-m(O)-(m([m]V)-m(O))- \\ -(m([m]V+[m]W)-m([m]V)) = 0\\$$

This implies that $c([m]W,[m]V)$ is const as a function of $X$ and so is $d(V,W)^m$, so $0=\text{div}(d(V,W)^m)=m\text{div}(d(V,W))\implies \text{div}(d(V,W)) = 0$. And so $d(V,W)$ is const as well.

b.

Follows immediately from $(a)$

c.

Note that since $W \in E[m^2]$ $[m](W+[m]U)=[m]W$ so

$$d(V,W+[m]U)=\frac{g_{[m]V+[m]W}(X)}{g_{[m]V}(X)g_{[m]W}(X-V)}=d(V,W)$$

d.

$$d(V+[m]U,W)=\frac{g_{[m]V+[m]W}(X)}{g_{[m]V}(X)g_{[m]W}(X-V-[m]U)}= \\ \frac{g_{[m]V+[m]W}(X)}{g_{[m]V}(X)g_{[m]W}(X-V)}\cdot \frac{g_{[m]W}(X-V)}{g_{[m]W}(X-V-[m]U)} = \\ d(V,W)e_n([m]U,[m]W)$$

For the last equation assume $X'=X-V-[m]U$

e.

First consider some equations for $U, V, W$

$$g_{[m]U+([m]V+[m]W)}(X)=d(U,V+W)g_{[m]U}(X)g_{[m]V+[m]W}(X-U)= \\ d(U,V+W)d(V,W)g_{[m]U}(X)g_{[m]V}(X-U)g_{[m]W}(X-U-V)$$

On the other hand:

$$g_{([m]U+[m]V)+[m]W}(X)=d(U+V,W)g_{[m]U+[m]V}(X)g_{[m]W}(X-U-V)= \\ d(U+V,W)d(U,V)g_{[m]U}(X)g_{[m]V}(X-U))g_{[m]W}(X-U-V)$$

Equating these two and cancelling common terms:

$$d(U,V+W)d(V,W)=d(U+V,W)d(U,V)$$

Now we can make the same equality but permute $U,V,W$ to $V,U,W$:

$$d(V,U+W)d(U,W)=d(U+V,W)d(V,U)$$

Dividing these two equations:

$$\frac{d(U,V)}{d(V,U)}=\frac{d(V,W)}{d(U,W)}\frac{d(U,V+W)}{d(V,U+W)}$$

Finally for $U,W,V$:

$$d(U,V+W)d(W,V)=d(U+W,V)d(U,W) \implies \\ \frac{d(U,V+W)}{d(U,W)}=\frac{d(U+W,V)}{d(W,V)}$$

So:

$$\frac{d(U,V)}{d(V,U)}=\frac{d(V,W)}{d(U,W)}\frac{d(U,V+W)}{d(V,U+W)}= \\ \frac{d(V,W)d(U+W,V)}{d(W,V)d(V,U+W)}$$

e.

Assume $S, T \in E[m]$ and choose $U, V \in E[m^2]: [m]U=S, [m]V=T$. Note that the left-hand side in $(d)$ does not depend on $W$, so we can use $W=[j]U$ to get the following:

$$\frac{c([n]U, [n]V)}{c([n]V, [n]U)}\overset{(b)}=(\frac{d(U,V)}{d(V,U)})^n \overset{(d)}=\prod_{j=0}^{m-1}\frac{d(V,[j]U)d(U+[j]U,V)}{d(V,U+[j]U)d([j]U,V)}$$

Note that the above terms are a translation-by-U from below terms so they all cancel except the first and the last one, that is $j=0$ and $j=m-1$:

$$\frac{c([n]U, [n]V)}{c([n]V, [n]U)} = \frac{d(V,O)d([m]U, V)}{d(V,[m]U)d(O,V)}$$

Now turning back to $(c)$ assume $W=O$ then $d(V,[m]U)=d(V,O)$. Next in $(d)$ set $V=O, W=V$ to get $d([m]U,V)=d(O,V)e_m([m]U,[m]V)$ this result in

$$e_m([m]U,[m]V)=\frac{c([m]U,[m]V)}{c([m]V,[m]U)} \implies \\ e_m(S,T)=\frac{c(S,T)}{c(T,S)}$$

f.

We now know that

$$e_m(S,T)=\frac{c(S,T)}{c(T,S)}=\frac{f_T(X)f_S(X-T)}{f_S(X)f_T(X-S)}$$

Pick $X_0 \in E$ so that the following two divisors have disjoint support. Define

$$D'_S = (S)-(O), D'_T=(X_0)-(X_0-T) \implies \\ \text{sum}(D'_S)=S,\text{sum}(D'_T)=T$$

Then define:

$$F'_S:=f_S(X), F'_T:=\frac{1}{f_T(X_0-X)} \implies\\ \text{div}(F'_S)=m(S)-m(O)=mD_S' \\ \text{div}(F'_T)=m(X_0) - m(X_0-T) = mD_T'$$

So

$$e_m(S,T)=\frac{F'_S(D'_T)}{F'_T(D'_S)}$$

Thus the we proved the theorem for specific divisors. Now let's prove it for general divisors. Consider arbitrary divisors $D_T$ and $D_S$ such that

$$\text{sum}(D_S)=S, \text{sum}(D_T)=T$$

From $(4.2.4)$ we know that

$$\exists h_1, h_2 \in F(E): D_S=\text{div}(h_1)+D'_S, D_T=\text{div}(h_2)+D'_T$$

Define

$$F_S:=F'_Sh_1^m,F_T:=F'_Th_2^m \implies \\ \text{div}(F_S)=\text{div}(F'_S)+m\text{div}(h)=mD'_S+m\text{div}(h)=mD_S \\ \text{div}(F_T) = mD_T$$

First assume that $\text{supp}(D'_S + D_S) \cap \text{supp}(D'_T + D_T) = \empty$ then

$$\frac{F_T(D_S)}{F_S(D_T)}=\frac{h_2(D_S)^mF'_T(D_S)}{h_1(D_T)^mF'_S(D_T)}=\frac{h_2(\text{div}(h_1))^mh_2(D'_S)^mF'_T(\text{div}(h_1))F'_T(D'_S)}{h_1(\text{div}(h_2))^mh_1(D'_T)^mF'_S(\text{div}(h_2))F'_S(D'_T)}$$

By $(4.3.4)$:

$$h_1(\text{div}(h_2))=h_2(\text{div}(h_1)) \\ h_2(D'_S)^m=h_2(mD'_S)=h_2(\text{div}(F'_S))=F'_S(\text{div}(h_2)) \\ h_1(D'_T)^m=F'_T(\text{div}(h_1))$$

So we have:

$$e_m(S,T)=\frac{F_T(D_S)}{F_S(D_T)}=\frac{F'_T(D'_S)}{F'_S(D'_T)}$$

Finally if $\text{supp}(D'_S + D_S) \cap \text{supp}(D'_T + D_T) \ne \empty$ then define:

$$D''_S=(X_1+S)-X_1, D''_T=(Y_1+T)-(Y_1)$$

And choose $X_1 \in E$ and $Y_1 \in E$ such that $\text{supp}(D'_S + D''_S) \cap \text{supp}(D'_T + D''_T) = \empty$ and $\text{supp}(D''_S + D_S) \cap \text{supp}(D''_T + D_T) = \empty$. Then by the argument above:

$$e_m(S,T)=\frac{F_T(D_S)}{F_S(D_T)}=\frac{F'_T(D'_S)}{F'_S(D'_T)}=\frac{F''_T(D'_S)}{F''_S(D'_T)}$$

$\square$

Embedding degree

So now we know about $E[r]$ in $E$ let's expore the behavior of rational points $E[r]_{\mathbb F_q}$. First thing to notice is that if $r \nmid |E_{\mathbb F_q}|$ that we cannot have an element of order $r$ and so $E[r]_{\mathbb F_q} = \empty$. So we assume $r \mid E_{\mathbb F_q}$ then by $(2.2.34)$ there's an element of order $r$ so we have at least one non-trivial subgroup of order $r$ that will correspond to $\lang (0,1) \rang_G$.

If we have just one element from another subgroup then from the subgroup structure above it's clear that will have all $r$-torsion in $E_{\mathbb F_q}$ and thus all $r+1$ subgroups.

Now note that if we start extending $\mathbb F_q$ to $\mathbb F_{q^2}$, $\mathbb F_{q^3}$ and so on, eventually we'll arrive at $\overline F$ that has all torsion inside (embedded). So it's clear there's some number $k: E[r] \nsubseteq E_{\mathbb F_{q^{k-1}}}, E[r] \subseteq E_{\mathbb F_{q^{k}}}$. This number $k$ is called embedding degree of $r$ which we'll shortly after the following definition:

def: Group of r-th roots in a field

$$\begin{align*} &\sphericalangle \\ &\mathbb F_q \in \mathcal F \\ \hline \\ &\mu_r:=\{x \in F: x^r=1\} \end{align*}$$

Recall that this group is cyclic that it has a generator called primitive r-th root of unity.

Proposition 4.3.6: Embedding degree

$$\begin{align*} &\sphericalangle \\ &q = p^n, p \in \mathfrak P \\ &(E, O)/\mathbb F_q \in \mathcal E \\ &r \in \mathfrak P, r \mid |E_{\mathbb F_q}|, r \nmid q-1 \\ \hline \\ &\text{The following } k\text{ are the same:} \\ &\begin{align*} &k=\argmin_k E[r] \subseteq E_{\mathbb F_{q^k}} \hspace{0.5cm} \tag{a}\\ &k=\argmin_k \mu_r \subseteq \mathbb F_{q^k} \hspace{0.5cm} \tag{b}\\ &k=\argmin_k r \mid q^{k}-1 \hspace{0.5cm} \tag{c}\\ \end{align*} \end{align*}$$

Proof

$(a) \implies (b)$

Assume $e_r(E[r],E[r])=\mu_d \subseteq \mu_r$. This implies that:

$$\forall S, T \in E[r]:1=e_r(S,T)^d=e_r([d]S,T) \overset{(4.3.5.h)}\implies \forall S \in E[r]: [d]S=O$$

So $|[d]^{-1}(O)|=|E[r]|=r^2$ thus by $(4.2.7)$ we have $d=r$.

Finally since $E[r] \subseteq E_{\mathbb F_{q^k}}$ we have $\forall \sigma \in \text{Gal}_{\overline F/\mathbb F_{q^k}} \subseteq \text{Gal}_{\overline F/\mathbb F_q}, \forall S \in E_{\mathbb F_{q^k}}: S^{\sigma}=S$. Next $\forall x \in \mu_m: \exists P, Q \in E_{\mathbb F_{q^k}}: x=e(P,Q)$. Finally by $(4.3.3.e)$:

$$x^\sigma = e(P,Q)^{\sigma}=e(P^{\sigma}, Q^{\sigma})=e(P,Q)=x$$

So we have $\mu_r \subseteq \mathbb F_{q^k}$

$(b) \implies (c)$

$\mu_r$ is a multiplicative subgroup of $\mathbb F_{q^k}$ and $|\mu_r|=r$, $|\mathbb F_{q^k}^*|=q^k-1$

$(c) \implies (a)$

Since $r \in \mathfrak P$ by $(2.2.34)$ we know that $\exists P \in E[r]_{\mathbb F_q} \subseteq E_{\mathbb F_q}$ of exact order $r$. Now since $E[r]\cong \Z/r\Z \times \Z/r\Z$ there's a basis $\{P,T\}$ for $E[r]$.

Next if $q=p^n$ define $\phi = \rho^n$ - n-th power frobenius. Note that $\phi \in \text{Gal}(\overline {\mathbb F}_q/\mathbb F_q) = \lang \phi \rang, \text{Gal}(\overline {\mathbb F}_q/\mathbb F_{q^k}) = \lang \phi^k \rang$ so:

$$P^{\phi}=P, T^{\phi}=[a]P+[b]T, a,b \in \Z/r\Z$$

(for the last it's easy to check that $E[r]$ is Galois invariant).

As a next step consider the following:

$$e_r(P,T)^q=e_r(P,T)^{\phi}=e_r(P^{\phi},T^{\phi})=e_r(P,[a]P+[b]T) = \\ e_r(P,T)^b$$

Note that from the proof of $(a)$ we know that since $P, T$ is a basis then pairing for any points from $E[m]$ will be a power of $e_r(P,T)$. Also note for these statements we consider everything in a field $\overline{\mathbb F}_q$ so we don't need any additinal assumptions from $(a)$. Long story short this means that:

$$q = b \pmod r$$

So $T^{\phi}= [a]P+[q]T$ and we have:

$$T^{\phi^k}=[a(1+q+\ldots+q^{k-1})]P+[q^k]T$$

But $q^k=1\pmod r$ so $[q^k]T=T$ and since $q-1 \ne 0 \pmod r$ so $(1+q+\ldots+q^{k-1})=\frac{q^k-1}{q-1}=0 \pmod r$ so $T^{\phi^k}=T \implies T \in \mathbb F_{q^k}$.

$\square$

def: Embedding degree

$$\begin{align*} &\sphericalangle \\ &(E, O)/\mathbb F_q \in \mathcal E \\ &r \in \mathfrak P, r \mid |E_{\mathbb F_q}| \\ \hline \\ &\text{deg}_e(r):=\begin{cases} 1 \text{ if } r \mid q-1 \\ \text{Any condition of } (4.3.6) \text{ otherwise} \end{cases} \end{align*}$$

Tate pairing

Tate pairing is based on the ideas of Weil pairing but advances it two ways: first its second argument is not restricted to $E[r]$, second it's computed more efficiently since it only needs one $f_{r,Q}$ calculation unlike the Weil pairing.

We start with the defintion that is based on Weil pairing. Further we'll consider the following parameters:

$$q = p^m, p \in \mathfrak P \\ r \in \mathfrak P \\ k:=\text{deg}_e(r)\ \\ r \mid |E_{\mathbb F_q}|, r^2 \nmid |E_{\mathbb F_{q^k}}| \\ \rho_q := \rho^m$$

def: Tate pairing

$$\begin{align*} &\sphericalangle \\ &(E, O)/\mathbb F_q \in \mathcal E \\ &P \in E[r]_{\mathbb F_{q^k}} \\ &Q \in E_{\mathbb F_{q^k}} \\ &R \in E: [r]R=Q \\ \hline \\ &\text{Modified Tate pairing:} \\ &\tau_r: E[r]_{\mathbb F_{q^k}} \times E_{\mathbb F_{q^k}}/[r]E_{\mathbb F_{q^k}} \to \mu_r, \\ &P,Q \mapsto e_r(P,R-R^{\rho_q}) \\ &\text{Tate pairing:} \\ &\lang .\,,. \rang_r: E[r]_{\mathbb F_{q^k}} \times E_{\mathbb F_{q^k}}/[r]E_{\mathbb F_{q^k}} \to \mathbb F_{q^k}^*/\mathbb (F_{q^k}^*)^r, \\ &P,Q \mapsto \sqrt[r]{\tau_r(P,Q)} \end{align*}$$

note

Instead of a point $Q$ we should rather consider a coset $Q+[r]E_{\mathbb F_{q^k}}$ but we'll stick to individual points for simplicity.

Here where we'd like to have a property $r^2 \nmid |E_{\mathbb F_{q^k}}|$ so that if we pick points from a subgroup of $|E_{\mathbb F_{q^k}}|$ we end up having different points in $E_{\mathbb F_{q^k}}/[r]E_{\mathbb F_{q^k}}$. It's easy to check it strictly so let's do an example instead.

Assume $E\cong \Z/12\Z$ and consider $r=3, r^2 \nmid 12$. Then $E[3]=\{0,4,8\}$, in $E/[3]E=\Z/3\Z$ it will be $\{0,1,2\}=\Z/3\Z$.

On the other hand if $r=2, r^2 \mid 12$ then $E[2]=\{0,6\}$ and it is $\{0\}$ in $\Z/2\Z$.

note

Previously we discussed that $[r]$ is surjective but why then $[r]E_{\mathbb F_{q^k}} \ne E_{\mathbb F_{q^k}}$? The thing is that $[r]$ is surjective for $E$ over $\overline {\mathbb F}_{q^k}$.

Proposition 4.3.7: Tate pairing properties

$$\begin{align*} &\sphericalangle \\ &(E, O)/\mathbb F_q \in \mathcal E \\ &P_i \in E[r]_{\mathbb F_{q^k}} \\ &Q_i \in E_{\mathbb F_{q^k}}/rE_{\mathbb F_{q^k}} \\ \hline \\ &\begin{align*} &\text{Tate pairing is well-defined} \hspace{0.5cm} \tag{a}\\ &\tau_r(P_1+P_2, Q)=\tau_r(P_1, Q)+\tau_r(P_2, Q)\hspace{0.5cm} \tag{b} \\ &\tau_r(P, Q_1+Q_2)=\tau_r(P, Q_1)+\tau_r(P, Q_2)\hspace{0.5cm} \tag{c} \\ & (\forall P \in E[r]: e_m(P,Q)=1) \implies Q = O\hspace{0.5cm} \tag{d}\\ \end{align*} \end{align*}$$

Proof

a.

First we need to make sure that Weil pairing is defined and the definition is independent on the choice of $R$:

$$O = Q - Q^{\rho_q}=[r](R-R^{\rho_q}) \implies R-R^{\rho_q} \in E[r]$$

So Weil parinig is well-defined. Now consider $R':[r]R'=Q$ and define $T:=R'-R$. Then $[r]T=O \implies T \in E[r]$ so:

$$e_r(P, R'-R'^{\rho_q})=e_r(P, R-R^{\rho_q}+T-T^{\rho_q})= \\ e_r(P, R-R^{\rho_q})\frac{e_r(P, T)}{e_r(P, T^{\rho_q})}$$

Considering that $P=P^{\rho_q}$ we have:

$$e_r(P, T^{\rho_q})=e_r(P^{\rho_q}, T^{\rho_q})=e_r(P, T)^{\rho_q}=e_r(P, T) \implies \\ e_r(P, R'-R'^{\rho_q})=e_r(P, R-R^{\rho_q})$$

So we proved that the value is independent of the choice of $R$. The last thing we need to show is that if $Q'-Q=[r]U\in E[r]_{\mathbb F_{q^k}}$ then we have the same value. Consider some $R: [r]R=Q$ then $R':=R+U \implies Q'=[r]R'$ so

$$\tau_r(P, Q')=e_r(P, R'-R'^{\rho_q})=e_r(P, R-R^{\rho_q}+U-U^{\rho_q})= \\ e_r(P, R-R^{\rho_q})=\tau_r(P,Q)$$

b.

Obvious

c.

Consider $[r]R_1=Q_1$, $[r]R_2=Q_2$:

$$\tau_r(P, Q_1+Q_2)=e_r(P, R_1-R_1^{\rho_q}+R_2-R_2^{\rho_q})= \\ e_r(P, R_1-R_1^{\rho_q})e_r(P, R_2-R_2^{\rho_q})=\tau_r(P, Q_1)\tau_r(P, Q_2)$$

d.

We will not prove it here

$\square$

Now as in the Weil pairing we'd like to give an alternative definition that is more suitable for calculations and prove the equivalence. But first let's prove some proposition that will make sure that we have enough flexibility in choosing different divisors.

Proposition 4.3.8: Equivalent invariant divisors existence

$$\begin{align*} &\sphericalangle \\ &(E, O)/\mathbb F_q \in \mathcal E \\ &D_1: D_1^{\rho_q}=D_1 \\ & S \subseteq E, |S| < \infty \\ \hline \\ &\exists D: D^{\rho_q}=D, D \sim D_1, \text{supp}(D_1) \cap \text{supp}(D)= \empty \end{align*}$$

Proof

Assume $D=\sum c_j(P_j)$. Since there's an power $x$ of $q$ such that $P_j \in E_{\mathbb F_{q^x}}$ and this group is finite, we know that $\exists M: \forall j: [M]P_j=O$. Take some $m=1 \pmod M$ and take some $T \in E_{\mathbb F_{q^m}}$. Then $T^{\rho_q^m}=T$ so $\rho_q$ permutes $\{1, T^{\rho_q}, \ldots, T^{\rho_q^{m-1}}\}$. Now define

$$D:=\sum_{i=0}^{m-1} \sum_{j=1}^dc_j((P_j+T^{\rho^i_q})-(T^{\rho^i_q}))$$

Note that since $D_1^{\rho_q}=D_1$ we have $c_j^{\rho_q}=c_{j'}, P_j^{\rho_q}=P_{j'}$ but for each $c_j$ there's a whole set of $\{1, T^{\rho_q}, \ldots, T^{\rho_q^{m-1}}\}$ that is permuted to itself, so $D^{\rho_q}=D$.

Next, sice $m=1 \pmod M$ and $[M]P_j=0$:

$$\text{sum}(\sum_{i=0}^{m-1} (P_j+T^{\rho^i_q})-(T^{\rho^i_q}))=mP_j=P_j$$

So $\text{sum}(D_1-D)=0, \deg(D_1-D)=0$ which implies $D_1 \sim D$.

Finally note that if $D$ contains some point in $S$ then either $T^{\rho^i_q}$ or $P_j+T^{\rho^i_q}$ for some $i,j \in S$. This happens if T is in $\bigcup_{i}(\rho^i_q)^{-1}(S) \cup \bigcup_{i,j}(\rho^i_q)^{-1}(S-P_j)$ which has at most $m(d+1)s$ elements (where $s:=|S|$ is a finite consant). But notice that by $(4.2.11)$ we have $|E_{\mathbb F_q^m}|\ge q^m-1-2q^{m/2}$ so by increasing $m$ we see that the group is growing exponentially faster than the prohibited values for $T$. So by increasing $m$ we can pick the correct $T$ (remember that $T$ was arbitrary).

$\square$

Proposition 4.3.9: Invariant functions existence

$$\begin{align*} &\sphericalangle \\ &(E, O)/\mathbb F_q \in \mathcal E \\ &D \in \text{Div}^0(E) \\ &\text{sum}(D)=0\\ &D=D^{\rho_q} \\ \hline \\ &\exists f: \text{div}(f)=D, f^{\rho_q}=f \end{align*}$$

Proof

Take some $f_1: \text{div}(f_1)=D$. Then:

$$\text{div}(f_1^{\rho_q})=D^{\rho_q}=D=\text{div}(f_1) \implies \\ f_1^{\rho_k}/f_1 = c \in \overline{\mathbb F}_q^*$$

Now take some $d: c=d^{q-1}=d^{\rho_q}/d$. Then

$$(f_1/d)^{\rho_q}=f_1^{\rho_q}/d^{\rho_q}=cf_1/d^{\rho_q}=f_1/d$$

$\square$

Now that we know we're very flexible in terms of picking a good divisor, let's formulate the alternative definition.

def: Alternative definition of Tate pairing

$$\begin{align*} &\sphericalangle \\ &P \in E[r]_{\mathbb F_{q^k}}, \\ &Q \in E_{\mathbb F_{q^k}} \\ &D_P, D_Q \in \text{Div}^0(E) \\ &D_P/{\mathbb F}_{q^k}, D_Q/{\mathbb F}_{q^k} \text{ that is } D_P=D_P^{\rho_q},D_Q=D_Q^{\rho_q} \\ &\text{sum}(D_P)=P,\text{sum}(D_Q)=Q \\ &\text{supp}(D_P) \cap \text{supp}(D_Q) = \empty \\ &\text{supp}D_P \cap \text{supp}D_Q = \empty \\ \hline \\ &\lang P,Q \rang^a_r:= f_{r,P}(D_Q) \\ &\tau^a_n(P,Q)=f_{r,P}(D_Q)^{(q^k-1)/r} \end{align*}$$

Proposition 4.3.20: Alternative definition of Tate pairing

$$\tau^a_n(P,Q)=\tau_n(P,Q)$$

Proof

For this proof we'll assume that $q:=q^k$ where $k$ is embedding degree.

Take some point $R:[r]R = Q$ and function $g$:

$$\text{div}(g)=r(R)-(Q)-(n-1)(O)$$

Then

$$\text{div}(g^{\rho_q})=r(R^{\rho_q})-(Q)-(n-1)(O) \implies \\ \text{div}(g/g^{\rho_q})=r(R)-r(R^{\rho_q})$$

By $(4.3.8)$ if we assume $D_1=(P)-(O)$ we can pick $D_P$ such that it's disjoint from $Q, R, O$ and $\text{sum}(D_P)=P$ (remeber that equivalent divisors have the same sum).

Take some $f: \text{div}(f)=rD_P, f^{\rho_q}=f$ (we can do it by $(4.3.9)$). Now we use $(4.3.5)$ with $S=P, T=R-R^{\rho_q}, D_S=D_P, D_T=(R)-(R^{\rho_q}), F_S=f, F_T=g/g^{\rho_q}$ then:

$$\tau_r(P,Q)=e_r(P, R-R^{\rho_q})=\frac{(g/g^{\rho_q})(D_P)}{f((R)-(R^{\rho_q}))}= \\ \frac{g(D_P)}{g^{\rho_q}(D_P)}\frac{1}{f((R)-(R^{\rho_q}))}=\frac{g(D_P)}{g^{\rho_q}(D_P)}\frac{f(R^{\rho_q})}{f(R)} =\\ \frac{g(D_P)}{g^{\rho_q}(D_P^{\rho_q})}\frac{f^{\rho_q}(R^{\rho_q})}{f(R)}=\frac{g(D_P)}{f(R)} (\frac{f(R)}{g(D_P)})^{\rho_q}= \\ \frac{g(D_P)}{f(R)} (\frac{f(R)}{g(D_P)})^{q}=(\frac{f(R)}{g(D_P)})^{q-1}$$

Then note that:

$$\frac{f(R)^r}{f(Q)}\frac{f(O)}{f(O)^r}=f(\text{div}(g))=g(\text{div}(f))=g(D_P)^r \implies \\ (\frac{f(R)}{g(D_P)})^{r}=\frac{f(Q)}{f(O)}f(O)^{r} \overset{\text{raise to } (q-1)/r}\implies \\ \tau_r(P,Q) = (\frac{f(Q)}{f(O)})^{(q-1)/r}f(O)^{q-1}$$

We know that $f=f^{\rho_q}$ and $O=O^{\rho_q}$ so $f(O)^{\rho_q}=f(O) \implies f(O) \in \mathbb F_q$. Since $D_P$ is disjoint from $O$ it follows that $f(O) \in \mathbb F_q^*$ and so $f(O)^{q-1}=1$.

Now define divisor $D_Q:=(Q)-(O)$ it will have a disjoint support with $D_P$ by definition of $D_P$ and it follows:

$$\tau_r(P,Q) = f(D_Q)^{(q-1)/r}=\tau^a_r(P,Q)$$

$\square$

Miller algorithm

We see that in Tate pairing the only non-trivial thing to calculate is the function $f$ with divisor $r(P)-r(O), P \in E[r]$, . We'll define a Miller function:

$$\text{div}f_{r,P}=r(P)-([r]P)-(r-1)(O)$$

Note that this function has a divisor $r(P)-r(O)$ if $P \in E[r]$ but it's defined for other points of the curve as well.

Recall that the line through $P, Q$ and the tangent line through point $[r]P$ has a divisor:

$$l_{[r]P,P}=([r]P)+(P) + (-[r+1]P)-3(O) \\ l_{[r]P,[r]P}=2([r]P)+(-[2r]P)-3(O)$$

And vertical line passing though $[r]P$ has a divisor:

$$v_{[r]P}=([r]P)+(-[r]P)-2(O)$$

So:

$$\text{div}(l_{[r]P,P}/v_{[r+1]P})=([r]P)+(P)-([r+1]P)-(O)\\ \text{div}(l_{[r]P,[r]P}/v_{[2r]P})=2([r]P)-([2r]P)-(O)$$

And

$$\text{div}{f_{2r,P}}=2r(P)-([2r]P)-(2r-1)(O) = \\ (2r(P)-2([r]P)-2(r-1)(O))+2([r]P)-([2r]P)-(O)=\\ \text{div}(f^2_{r,P})\text{div}+(l_{[r]P,[r]P}/v_{[2r]P}) \implies \\ {f_{2r,P}}(x)=f^2_{r,P}(x)l_{[r]P,[r]P}(x)/v_{[2r]P}(x)$$

On the other hand for points $P$ and $Q$:

$$\text{div}{f_{r+1,P}}=(r+1)(P)-([r+1]P)-r(O)=\\ ([r]P-([r])P-(r-1)O +(P)) +([r]P)-([r+1]P) -(O)= \\ \text{div}f_{r,P}+\text{div}(l_{[r]P,P}/v_{[r+1]P}) \implies \\ f_{r+1,P}(x)=f_{r,P}(x)l_{[r]P,P}(x)/v_{[r+1]P}(x)$$

So we can use this fact to employ double and add algorithm for quickly finding $f_{r,P}(D_Q)$:

$$f_{1,P}(D_Q)=1 \\ f_{r+1,P}(D_Q)=f_{r,P}(D_Q)l_{[r]P,P}(D_Q)/v_{[r+1]P}(D_Q)\\ {f_{2r,P}}(D_Q)=f^2_{r,P}(D_Q)l_{[r]P,[r]P}(D_Q)/v_{[2r]P}(D_Q)$$

Ate pairing

Ate pairing is an optimization of Tate pairing aiming to reduce the Miller loop length.

First note that the divosor of $f_{a,O}$ is 0 and hence this function equals 1.

Next, we have the following equation for Miller function:

$$\text{div}(f_{ab, Q})=ab(Q)-([ab]Q)-(ab-1)(O) \\ \text{div}(f_{a,Q}^b)=ab(Q)-b([a]Q)-(ab-b)(O) \\ \text{div}(f_{b,[a]Q})=b([a]Q)-([ab]Q)-(b-1)(O) \implies \\ \text{div}(f_{ab, Q})= \text{div}(f_{a,Q}^b)+\text{div}(f_{b,[a]Q}) \implies \\ f_{ab, Q}(P)=f_{a,Q}^b(P)\cdot f_{b,[a]Q}(P)$$

Let's take some $\lambda = q \pmod r$ then since $q^k-1 = 0 \pmod r$ we have $\lambda^k-1 = 0 \pmod r$. So we can define $m:=(\lambda^k-1)/r$ and:

$$f_{\lambda^k, Q}(P)=f_{\lambda^k-1, Q}(P)l_{[\lambda^k-1]Q,Q}(P)/v_{[\lambda^k]Q}(P)= \\ f_{\lambda^k-1, Q}(P)l_{O,Q}(P)/v_{Q}(P)=f_{\lambda^k-1, Q}(P)=\\ f_{mr, Q}(P)$$

Let's raise both sides to $(q^k-1)/r:$

$$f_{\lambda^k, Q}(P)^{(q^k-1)/r}=f_{mr, Q}(P)^{(q^k-1)/r} = \\ f_{r, Q}(P)^{m(q^k-1)/r}f_{m, [r]Q}(P)=f_{r, Q}(P)^{m(q^k-1)/r}f_{m, O}(P)= \\ f_{r, Q}(P)^{m(q^k-1)/r}=\tau_r(Q,P)^m$$

Now assuming $a=\lambda, b = \lambda^{k-1}$, recursively applying the equation above ($f_{ab, Q}(P)=f_{a,Q}^b(P)\cdot f_{b,[a]Q}(P)$) and taking into account that $[\lambda^i]Q=[q^i]Q$:

$$f_{\lambda^k,Q}(P)=f_{\lambda,Q}^{\lambda^{k-1}}(P)\cdot f_{\lambda,[q]Q}^{\lambda^{k-2}}(P)\cdot \ldots \cdot f_{\lambda,[q^{k-1}]Q}^{\lambda}(P)$$

Next we want to take $Q \in \mathbb G_2$ - the trace-kernel subgroup and $P \in \mathbb G_1$ from trace-image subgroup. In this case:

$$f_{\lambda^k,Q}(P)^q=\phi(f_{\lambda^k,Q}(P))= \\ f_{\lambda^k,\phi(Q)}(\phi(P))=f_{\lambda^k,[q]Q}(P)$$

So we have:

$$f_{\lambda^k,Q}(P)=f_{\lambda,Q}(P)^{\sum_{i=0}^{k-1}\lambda^{k-1-i}q^i}$$

And:

$$\tau_r(Q,P)^m=(f_{\lambda,Q}(P)^{(q^k-1)/r})^{\sum_{i=0}^{k-1}\lambda^{k-1-i}q^i}$$

So if $r \nmid m$ we can define an Ate pairing with the same properties as in Tate pairing:

$$\alpha_{\lambda}: \mathbb G_1 \times \mathbb G_2 \to \mu_r, (P,Q) \mapsto f_{\lambda, P}(D_Q)^{(q^k-1)/r}$$

where $\lambda=q \pmod r$. This gives a shorter cycle for Miller loop than in Tate's case where you need $\log r$ iterations (here you need $\log \lambda$).

Twists

One final optimization that is frequently used is the so-called twists. This is essentially isomorphic curves for a given elliptic curve. Why do we need that? In general the higher the degree of the field the harder it's to make arithmetic calculations inside of it. For example $\mathbb F_{q^{12}}$ is much more computation intensive than $\mathbb F_q$. So if isomorphic curve has points a lower field that's something that we'd like to have.

Consider an equation

$$E: y^2=x^3+Ax+B, A, B \in \mathbb F_{q}$$

and an isomorphism of the form:

$$(x,y) \mapsto (x/u^2,y/u^3), u \in \mathbb F_{q^k}, \nexists v \in \mathbb F_{q^k}: v^2=u$$

Then the isomorphic equation will become:

$$E': y^2=x^3+Au^4x+u^6B$$

Now note that there are several cases for values of $u, A$ and $B$:

• $A=0, u^6 \in \mathbb F_{q^{k/6}}$, in this case $E' / {\mathbb F}_{q^{k/6}}$ and we say $d=6$ or we have sextic twist

• $A=0, u^6 \in \mathbb F_{q^{k/3}}$, in this case $E' / {\mathbb F}_{q^{k/3}}$ and we say $d=3$ or we have cubic twist

• $B=0, u^4 \in \mathbb F_{q^{k/4}}$ in this case $E' / {\mathbb F}_{q^{k/4}}$ and we say $d=4$ or we have quartic twist

• $u^2 \in \mathbb F_{q^{k/2}}$ in this case $E' / {\mathbb F}_{q^{k/2}}$ and we say $d=2$ or we have quadratic twist