# Pairings coming out

By [Lisa Akselrod](https://paragraph.com/@lisaakselrod) · 2025-01-20

---

Introduction
------------

I know we usually blackbox pairings calling them moonmath and putting e(dot,dot) instead. But enough is enough. This article explains the math behind pairings. It relies on the course on ECC led by [Matan Prasma](https://sites.google.com/view/matanprasmashomepage/publications) and [organized by PSE](https://www.youtube.com/watch?v=JYSQYaAhJYc&list=PLV91V4b0yVqQ_inAjuIB5SwBNyYmA9S6M) and [Carlos](https://x.com/CPerezz19) in particular.

How to read: the article consists of two parts: prerequisites and pairings. It might make sense to go to the section “Pairings” be surprised and then come back to the prerequisites but maybe you know better. All the proofs are skipped; you can find them in Matan’s textbook. Hope you have fun reading it!

Pairings after being blackboxed by web3 community since forever:

![](https://storage.googleapis.com/papyrus_images/88ecf547a5f99e7327d41cbf1c76b59d26fe26edd3e753f33be01eef633bfd2b.jpg)

### **Prerequisites**

I’ll assume the reader is aware of the intuition behind what an elliptic curve is as it pops up in many crypto write ups. Instead I will focus more on the properties and theorems affiliated with ECs that pairings rely on.

This write up also assumes that the reader is somehow fluent with groups, fields, and sets.

_Note: because of the math mode limitations i might use f\_bar to denote what’s usually denoted as f with bar over it._

### Prerequisites to prerequisites

*   Field characteristic – the smallest number of times you need to add the multiplicative identity to get the additive identity (i.e. the minimal number $$n ∈ N$$ such that $$1 + 1 + ... + 1 = 0$$).
    
*   Field closure – a field F is algebraically closed if every non-constant polynomial in $$F\[x\]$$ has a root in $$F$$.
    
*   Abelian group – a commutative group, a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written: $$f(x,y) = f(y,x)$$.
    

### Elliptic Curves

An elliptic curve in general Weierstrass form over a field K:

$$E ∶ y^2 + a\_1xy + a\_3y = x^3 + a\_2x^2 + a\_4x + a\_6$$ + some conditions (we are not really interested in this form).

We are interested in ECs of the _short_ Weierstrass form: those over fields whose characteristic is neither 2 nor 3. In this case the equation can be way simplified:

$$E ∶ y^2 = x^3 + Ax + B$$. We also require that A and B satisfy the following: $$∆(E) ∶= 4A^3 + 27B^2 ≠ 0$$.

The solution set (all zeros) to the ECs is a set of points of the form $$(x,y)$$ and in general it does not have any apparent geometry.

### The group law on an elliptic curve

Rude intuition: to make the solution set $$(x,y)$$’s work as a group we need to introduce some zero/neutral element. We introduce the point at infinity for this role. We denote the point at infinity as $$O$$ and can think of it $$O = {∞,∞}$$.

Let $$E ∶ y^2 = x^3 + Ax + B$$ be an elliptic curve over a field $$K$$. The **K-rational points** of $$E$$ are the set $$E(K) = {(x, y) ∈ K^2 ∣ y^2 = x^3 + Ax + B} ∪ {O}.$$

Let’s now define the group law (we do not provide the intuition of why it works this way, but if you want – check in [this book](https://drive.google.com/file/d/14ZOhQr4t-6Idd_ljeMCUexFQvCmd72cp/view)).

Take two points on EC: $$P = (x\_1, y\_1)$$ and $$Q = (x\_2, y\_2)$$ such that ​​$$P ≠ Q$$ and that none of them is the point at infinity $$O$$. We want to compute $$R’ = P + Q$$.

Define $$m = (y\_2 − y\_1)/(x\_2 − x\_1)$$ and $$x\_3 = m^2 − x\_1 − x\_2$$. Then $$P + Q = R' = (m^2 − x\_1 − x\_2, m(x\_1 − x\_3) − y\_1)$$.

$$P = Q$$ is a separate case. In this case, $$P + P = (m^2 − 2x\_1, m(x\_1 − x\_3) − y\_1)$$. Finally, to consider the point at infinity: $$P + O = P$$ and $$O + O = O$$.

### Theorem

Let $$E ∶ y^2 = x^3 + Ax + B$$ be an elliptic curve defined over a field K with $$char(K) ≠ 2, 3$$. Then the K-rational points $$E(K) = {(x, y) ∈ K × K ∣ y^2 = x^3 + Ax + B} ∪ {O}$$, together with addition of points defined above, form an abelian group. The neutral element is $$O$$ and the inverse of a point $$P = (x\_1, y\_1)$$ is given by $$−P = (x\_1,−y\_1)$$.

### Rational functions

A rational function is a function of the form $$r(x,y) = f(x)/g(x)$$ where both f and g are polynomials and $$g ≠ 0$$.

The field of rational functions is the set $K(x,y) = {f(x,y)/g(x,y) ∣ f, g ∈ K\[x,y\], g ≠ 0} $together with the obvious addition and multiplication. We use two-var polynomials as it’s what we are interested in for ECs.

Every field element of this type defines a map $$(x\_0, y\_0) ↦ f(x\_0,y\_0)/g(x\_0,y\_0)$$. Fyi: the map is a partial function as it’s not defined for points such as $$g(x\_0, y\_0) = 0$$.

A rational function $$r(x, y)$$ is **regular** at point $$P = (x\_0, y\_0)$$ if there exists a representation of $$r$$ as $$r = f/g$$ with $$g(P) ≠ 0$$ (we can also say if it is defined at point $$P$$).

### Polynomials over ECs

#### Set of polynomials

For an elliptic curve $$E/K ∶ y^2 = x^3 + Ax + B$$ we define the **set of polynomials** over E to be $$K\[E\] = K\[x,y\]/(y^2 − x^3 − Ax − B = 0)$$. One can think of polynomials over EC as reminders of division even though for the case of polynomials in two variables there is no explicit way to divide polynomial over polynomial.

#### Canonical form

The **canonical form** of a polynomial is $$f(x, y) = v(x) + yw(x)$$ for some $$v, w ∈ K\[x\]$$ (i.e. $$v$$ and $$w$$ are polynomials in one variable). This form helps us to represent polynomials in two variables as polynomials in one variable. The canonical form is unique.

*   The **conjugate** of $$f$$ is $$\\bar{f}$$ $$= v(x) − yw(x)$$.
    
*   The **norm** of f is $$N\_f = f ⋅ \\bar{f}$$.
    
*   The **degree** of $$f$$ is $$deg(f) = max{2 ⋅ deg\_x(v), 3 + 2 ⋅ deg\_x(w)}$$.
    

Useful properties:

*   $$deg(f) = deg\_x(N\_f )$$: the degree of the polynomial equals the degree of the norm.
    
*   $$deg(f ⋅ g) = deg(f) + deg(g)$$.
    

#### Rational functions over EC

For an elliptic curve $$E/K$$ the set of rational functions on $$E$$ is the quotient set $$K(E) = K\[E\] × K\[E\]∖ {0}/ ∼$$ where $$∼$$ stands for the equivalence relation $$(f, g) ∼ (h, k) ↔ f ⋅ k = h ⋅ g ∈ K\[E\]$$. To check if equality holds, we can write $$f ⋅ k$$ and $$h ⋅ g$$ in canonical forms and compare coefficients.

Observation: $$K(E)$$ is a field.

### Zeros and poles

Let $$E/K$$ be an elliptic curve, and let $$r ∈ K(E)$$ be a rational function. We say that $$r$$ has a **zero** at $$P ∈ E(K)$$ if $$r(P) = 0$$ and that $$r$$ has a **pole** at $$P$$ if $$r$$ is not regular at $$P$$ (i.e. there is no representation $$r = f/g ∈ K(E)$$ such that $$g(P) ≠ 0$$).

### Multiplicity

In the one variable case, $$r(x) =f(x)/g(x)$$ and we say that $$x\_0$$ is **a zero of r of multiplicity n** if $$(x − x\_0)^n$$ divides $$f(x)$$ but $$(x − x\_0)^{(n+1)}$$ does not divide $$f(x)$$. The same for the pole but with $$g(x)$$ instead of $$f(x)$$.

For two variable rational functions cases it’s not that straightforward. We can think of zero as a point of intersection of the elliptic curve $$E$$ and a curve $$C\_f: f(x,y) = 0$$ (the same for the pole but with $$C\_g: g(x,y) = 0$$). Now we want to derive a definition of multiplicity of zeros and poles.

#### Introducing uniformizer

Let $$E/K$$ be an elliptic curve and $$P ∈ E$$. A rational function $$u ∈ K(E)$$ with $$u(P) = 0$$ is called a **uniformizer** at $$P$$ if $$∀r ∈ K(E) ∖ {0}$$, $$∃d ∈ Z$$ and $$s ∈ K(E)$$ with $$s(P) ≠ 0,∞$$, such that $$r = u^d ⋅ s$$.

(As a rude intuition: for some rational function r that has problems at $$P$$ (zero or pole), a uniformizer for $$P$$ is a rational function $$u$$ with a zero at $$P$$, such that for any rational function $$r$$ that is ”complicated” at $$P$$, we can find a rational function s that is not complicated at $$P$$).

The uniformizers we present below are simply one common choice:

*   Let $$E/K$$ be an elliptic curve and $$P = (a, b) ∈ E(K)$$ a finite point with $$2P ≠ O$$. Then the rational function $$u(x, y) = x − a ∈ K(E)$$ is a uniformizer at $$P$$.
    
*   For $$P ∈ E(K) ∖ {O}$$ such that $$2P = O$$, the rational function $$u(x, y) = y ∈ K(E)$$ is a uniformizer at $$P$$.
    
*   For $$P = O$$, the function $$u(x, y) = x/y$$ is a uniformizer.
    

Remarks on uniformizers:

*   Uniformizers exist for all points in $$E(K)$$.
    
*   Even for a fixed point $$P ∈ E(K)$$ there is usually more than one uniformizer at $$P$$.
    
*   The number $$d$$ (in $$r = u^d ⋅ s$$) does not depend on the choice of the uniformizer.
    
*   We say that $$r$$ has **order/multiplicity** $$d$$ at $$P: ord\_P(r) = d$$.
    

#### More on the order

Note that we have two different definitions of order at P:

![](https://storage.googleapis.com/papyrus_images/e595459bca237f568d8eda8148843852d6d67d5ad659562ff1069e6c504b7ce9.jpg)

1.  The first is the order of P as an element in the abelian group E(K), i.e. the minimal integer n such that nP = O.
    
2.  The second one we’ve just described above in which we say that P has order n with respect to r.
    

(In this write up we are mostly dealing with the second definition).

Remarks about order:

*   A point $$P ∈ E(K)$$ has order $$ord\_P(r) = 0$$ if and only if it is neither a zero or a pole of $$r$$.
    
*   We can add and multiply rational functions at $$P$$ if they are finite at $$P$$: for $$r, s ∈ K(E)$$ such that $$r(P)$$ and $$s(P)$$ are finite we have $$(r ⋅ s)(P) = r(P)⋅s(P)$$ and $$(r + s)(P) = r(P) + s(P)$$.
    
*   If $$P$$ is a zero of r (i.e. $$r(P) = 0$$) then $$ord\_P (r) > 0$$ and if $$P$$ is a pole of $$r$$ (i.e. $$r(P)$$ is not defined) then $$ord\_P (r) < 0$$.
    
*   Let $$r, r′ ∈ K(E)$$ be rational functions and $$P ∈ E(K)$$. Then $$ord\_P(r⋅r') = ord\_P(r) + ord\_P(r')$$ and for $$r' ≠ 0, ord\_P(r/r') = ord\_P(r) − ord\_P(r')$$.
    
*   At point of infinity, $$ord\_O(f) = −deg(f)$$
    
*   Sum of multiplicities of roots equal degree: $$deg(f) = ∑ ord\_P(f)$$ for all $$P∈E$$ such that $$f(P)=0$$.
    
*   A rational function $$r ∈ K(E)$$ has only finitely many zeros and poles.
    
*   The sum of orders is zero. Let $$E/K$$ be an elliptic curve over an algebraically closed field $$K$$. For $$r ∈ K(E) : ∑ ord\_P(r) = 0$$ for all $$P∈E(K)$$.
    

(These remarks are mostly used in proofs so here they might look random but they are illustrative to show how much we are dealing with the order).

### Encoding zeros and poles with their multiplicities in a formal manner

#### Divisors

Informally, divisor is a formal sum of all zeros and poles. Formally, a **divisor** on $$E$$ (over $$K$$) is an expression $$D = ∑n\_P \[P\]$$ for all $$P ∈E(K)$$ where $$∀P, n\_P ∈ Z$$ are multiplicities/degrees at the points and only finitely many $n\_P $’s are non-zero.

$$Div\_K(E)$$ the set of all divisors on $$E$$. This set is a group with addition as the group law. The neutral element is the divisor $$∑ 0 ⋅ \[P\]$$ and the inverse of a divisor $$D = ∑n\_P \[P\]$$ is the divisor $$−D = ∑ −n\_P \[P\]$$.

*   The **degree** **of a divisor** $$D ∈ Div\_E$$ is $$deg(D) = ∑n\_P$$ and the sum of a divisor $$D ∈ Div\_E$$ is $$sum(D) = ∑n\_P ⋅ P ∈ E(K)$$.
    
*   The **norm** of a divisor $$D = ∑ n\_p\[P\]$$ is $$∣D∣ = ∑∣n\_P∣$$ for all $$P ∈E∖{O}$$.
    
*   For $$r, s ∈ K(E) ∖ {O}$$ rational functions, $$div(r⋅s) = div(r) + div(s)$$ and $$div(r/s) = div(r) − div(s)$$.
    

Astonishing fact: $$∑ ord\_P(r) ⋅ P = O$$ (in other words the number of zeros equals the number of poles).

The divisor $$D$$ is **principle** if and only if

*   $$deg(D) = 0$$;
    
*   $$sum(D) = 0$$.
    

(Also famous as Abel-Jacobi)

If $D\_1 - D\_2 $is principal, then we say that $$D\_1, D\_2 ∈ Div(E)$$ are **linearly equivalent** or in the same divisor class.

Other divisor properties:

*   $$div(−r) = div(r)$$
    
*   $$−div(r) = div (1/r)$$
    

**Line on EC**

A line on $$E$$ is a polynomial in $$K\[E\]$$ of the form $$l(x, y) = αx + βy + γ$$ with $$α, β, γ ∈ K$$ and $$α ≠ 0$$ or $$β ≠ 0$$. For $$P\_1, P\_2 ∈ E$$ finite with $$P\_1 ≠ P\_2$$ there is a line through $$P\_1$$ and $$P\_2$$. For $$P = (a, b) ∈ E\_{A,B}$$ finite and not of order two, the line $$l(x, y) = m(x − a) − (y − b)$$ with $$m = (3a^2+A)/2b$$ has a double zero at $$P$$ and one other finite zero. In other words: $$∃Q ∈ E ∶ div(l) = 2\[P\] + \[Q\] − 3\[O\]$$.

**Classification of divisors of lines**

Suppose $$E/K$$ be an elliptic curve over an algebraically closed field. Let $$l$$ be a line on $$E$$. Then there are distinct finite points $$P\_1, P\_2, P\_3$$ on $$E$$ such that one of the following holds:

1.  $$div(l) = \[P\_1\] + \[P\_2\] + \[P\_3\] − 3\[O\]$$
    
2.  $$div(l) = 2 \[P\_1\] + \[P\_2\] − 3\[O\]$$
    
3.  $$div(l) = 3 \[P\_1\] − 3\[O\]$$
    
4.  $$div(l) = \[P\_1\] + \[P\_2\] − 2\[O\]$$
    
5.  $$div(l) = 2 \[P\_1\] − 2\[O\]$$
    
    Moreover, there is a line for each of these divisors that furthermore satisfy sum$$(div(l)) = O$$.
    

For each $$D ∈ Div^0(E)$$, there is a unique point $$P ∈ E$$ such that $$D ∼ \[P\] − \[O\]$$

**Rational maps**

A rational map $$ρ ∶ E → E$$ is a pair $$ρ = (r, s)$$ where $$r, s ∈ K(E)$$ are rational functions on $$E$$ and $$K$$ is algebraically closed such that for all $$P ∈ E(K), s(P)^2 = r(P)^3 + Ar(P) + B$$. And $$r(P) = ∞$$ if and only if $$s(P) = ∞$$.

A rational map $$ρ = (r, s) ∶ E → E$$ induces a map $$ρ ∶ E(K) → E(K)$$ given by $$P ↦ (r(P), s(P))$$ if $$r(P), s(P) ≠ ∞$$ and $$P ↦ O$$ if $$r(P) = s(P) = ∞$$.

(If you wonder why we distinguish between rational maps and rational functions as two different creatures – the reason is to avoid calling two different things ‘rational functions’ tho we could. There is always the problem of notation abuse whatever we are doing).

**Torsion subgroups**

The n-torsion points of $$E$$ are $$E\[n\] = {P ∈ E(K) ∶ n ⋅ P = O}$$. Informally, we can say that these are all points on the curve such that while added to itself n times we get zero.

(btw we are really close to pairings now!)

**The Divisor of $$g\_m − g\_n$$**

Now we want the divisor of $$g\_m - g\_n$$ but we can’t just go and take it. More work is required.

Let $$Dr$$ be the derivative of a rational function $$r$$ (but $$D$$ has been a divisor 5 min ago? Sorry so many words start with D. What are we expected to do?)

In this piece we omit the precise definition of derivative of a rational function, but if you remember the derivative of a function in two variables – that’s approx it.

Derivative also has an order: let $$r$$ be a rational function. If $$ord\_p(r) = d ≠ 0$$ is prime to $$p$$, then $$ord\_p(Dr) = d − 1$$.

Now we want the derivatives of $$g\_n$$ and $$h\_n$$: we have $$Dg\_n = 2nh\_n$$ and $$Dh\_n = n(3g^2\_n + A)$$.

We also need a rational function that will operate as a uniformizer at $$(P − Q)$$: suppose $$u$$ is a uniformizer at $$P$$. Then the rational function $$T\_Q(u)$$ defined by $$\[T\_Q(u)\] (R) = u(R + Q)$$ is a uniformizer at $$P − Q$$.

Finally we can have $$div(g\_m − g\_n)$$:

Say we write $$⟨E\[n\]⟩$$ to denote the divisor whose nonzero entries are the points of $$E\[n\]$$, each with coefficient one. Then $$div (g\_m − g\_n) = ⟨E\[m + n\]⟩ + ⟨E\[m − n\]⟩ − 2⟨E\[m\]⟩ − 2⟨E\[n\]⟩$$. This thing also has quite a long and entertaining proof if you are into things like that.

### Number of points on EC

If n is prime to $$p$$, then $$E\[n\]$$ has $$n^2$$ points.

To approach pairing (or at least to poke them) we want to rely on the fact that $$E\[n\] ≅ Z\_n ⊕ Z\_n$$ where $$≅$$ stands for isomorphic. It has a long and entertaining proof.

Pairings coming out
-------------------

We are ready to construct pairings. We are going to use ‘facts’ discussed earlier step by step and hope it looks somehow logical. If it doesn’t – please blame yourself and only yourself.

*   Let $$E/K$$ be an elliptic curve over an algebraically closed field with char $$K = p$$.
    
*   Recall that for an integer $$n$$ prime to $$p$$ we have an isomorphism $$E\[n\] ≅ Z\_n ⊕ Z\_n$$.
    
*   Let $$Q ∈ E\[n\]$$ be a point on EC and $$f\_Q ∈ K(E)$$ be a rational function such that the divisor of the rational function $$div(f\_Q) = n\[Q\] − n\[O\]$$.
    
*   Take the map $$\[n\] ∶ E(K) → E(K)$$ given by $$P ↦ nP$$ (it might look somehow affiliated with n-Torsion points hope you still remember them!)
    
*   This map is surjective.
    
*   Let $$Q'∈ E\[n^2\]$$ be such that $$nQ' = Q$$.
    
*   Consider the divisor $$D\_Q' = ∑(\[Q' + R\] − \[R\])$$ .
    
*   The degree of $$D$$ is 0 and since $$#E\[n\] = n^2, ∑(Q' + R − R) = n^2Q' = O$$.
    
*   So there exists a rational function $$g = g\_Q ∈ K(E)$$ such that $$div(g\_Q) = ∑(\[Q' + R\] − \[R\])$$
    
*   Consider the rational function $$f\_Q ○ \[n\] ∈ K(E)$$.
    
*   The points $$R ∈ E\[n\]$$ are poles of $$f\_Q ○ \[n\]$$ of order $$n$$ each.
    
*   The points $$X = Q’ + R$$ for $$R ∈ E\[n\]$$ are those points $$X$$ for which $$nX = Q$$.
    
*   It follows that $$div(f\_Q ○ \[n\])=n∑(\[Q' + R\]) − n(∑\[R\]) = div(g\_Q^n)$$
    
*   Thus, $$f\_Q ○ \[n\]$$ is a constant multiple of $$g^n\_Q$$ and wlog, we may choose $$f\_Q$$ such that $$f\_Q ○ \[n\] = g^n\_Q$$.
    
*   Let $$P ∈ E\[n\]$$, an n-torsion point, and $$S ∈ E(K)$$, a point on EC. Then $$g\_Q(S + P)^n = f\_Q (n(S + P)) = f\_Q(nS) = g\_Q(S)^n$$
    
*   so that $$g\_Q(S + P)^n/g\_Q(S)^n = 1$$.
    

**Finally!!!!!!!!!!**

Weil pairing, this is this guy: $$e\_n(P, Q) = g\_Q(S + P)/g\_Q(S)$$ and thus get a function $$e\_n ∶ E\[n\] × E\[n\] → K$$.

Maybe it’s not what you expected (if you expected anything at all). In particular, pairing depends on the choice of the function g\_Q. And what is that function? Remember several rows above we told “...wlog, we may choose $$f\_Q$$ such that $$f\_Q ○ \[n\] = g^n\_Q$$…” If we stick to the math mindset we should say ‘AH that’s details of implementation we don’t care!’

But we are not that mean so let’s provide one example taken from a random textbook:

For an EC $$𝑌^2 =𝑋^3+2𝑋^2−3𝑋$$

Functions g:

![](https://storage.googleapis.com/papyrus_images/8718a8594fdc08c2924541a4f0cbf7794ef02cc2fcae3c7cdf1a17eb9568e7d3.png)

But these are not those functions $$g$$ but some other functions $$g$$, using their divisors one calculated functions $$f$$:

![](https://storage.googleapis.com/papyrus_images/3537170a18e3044ae2941a0c7ad14bb479594f90fd598a565dc00a96a3fc4d5c.jpg)

And then these functions $$f$$ are utilized to calculate the pairing:

![](https://storage.googleapis.com/papyrus_images/2fbe3f9e017959ece2e5100d287afd211498d19e69552d5e6056c697f1652cb6.jpg)

[https://crypto.stackexchange.com/questions/48865/bilinear-form-weil-pairing](https://crypto.stackexchange.com/questions/48865/bilinear-form-weil-pairing)

### Conclusion

So pairings are some manipulation with polynomials and divisors. Even if the explanation was vague one definitely can see that there is no real magic there it’s just math.

Usually we are all somehow used to polynomial manipulations but divisors are a new creature for us. So understanding pairings heavily relies on understanding divisors and feeling fluent with these guys.

For proofs check [the textbook](https://sites.google.com/view/matanprasmashomepage/publications). For detailed awesome explanations see [the course](https://www.youtube.com/watch?v=JYSQYaAhJYc&list=PLV91V4b0yVqQ_inAjuIB5SwBNyYmA9S6M).

---

*Originally published on [Lisa Akselrod](https://paragraph.com/@lisaakselrod/pairings-coming-out)*