# Divisors on elliptic curves

Divisors on elliptic curves are important in pairing-based cryptography. They’re useful because the structure that an elliptic curve provides lets you reduce sums of divisors down to simpler sums.

Suppose that we have several divisors

D_{1}= (P_{1}) – (O)

D_{2}= (P_{2}) – (O)…

D= (_{n}P) – (_{n}O)

We can always add the divisors *D*_{1} through *D _{n}* to get

D=D_{1}+ …+ D_{n}

=(P_{1}) + … + (P) +_{n}n(O)

but this gets unwieldy very quickly.

In particular, for cryptographic applications, we want to use a value of *n* that has at least 160 bits, and we certainly don’t want to think about manipulating a divisor that has 2^{160} terms. Fortunately, elliptic curves provide the structure needed to make a calculation like this feasible because they provide a way to reduce a sum of the form (*P*_{1}) – (*O*) + (*P*_{2}) – (*O*) to another divisor of the form (*Q*) – (*O*), which keeps the number of terms manageable. Here’s how we can do this.

Suppose that *P*_{1} and *P*_{2} are two points on an elliptic curve and that *P*_{3} = *P*_{1} + *P*_{2}. Let *u* be the line through *P*_{1}, *P*_{2} and –*P*_{3}, and let *v* be the line through *P*_{3} and –*P*_{3}.The following picture shows how this looks.

Now let's think of points on the elliptic curve as poles and zeroes that define a divisor, so that *u* has zeroes at *P*_{1}, *P*_{2} and –*P*_{3} plus a pole of order 3 at *O* and *v* has zeroes at *P*_{3 }and –*P*_{3} plus a pole of order 2 at *O*. This means that we can write

div(

u) = (P_{1}) + (P_{2}) + (–P_{3}) – 3(O)

and

div(

v) = (P_{3}) + (–P_{3}) – 2(O)

Now note that we look at div(*u*) – div(*v*) we find that

div(

u) – div(v) = (P_{1}) + (P_{2}) + (–P_{3}) – 3(O) – ((P_{3}) + (–P_{3}) – 2(O))= (

P_{1}) + (P_{2}) – (P_{3}) – (O)= [(

P_{1}) – (O)] + [(P_{2}) – (O)] – [(P_{3}) – (O)]

or that

[(

P_{1}) – (O)] + [(P_{2}) – (O)] = (P_{3}) – (O) + div(u/v)

So if *D*_{1} = (*P*_{1}) – (*O*) and *D*_{2} = (*P*_{2}) – (*O*), this gives us a way to find *D*_{1} + *D*_{2} in a way that keeps the sum in the form (*Q*) – (*O*). If we apply this trick again and again, this gives a way to calculate a sum like *D* = *D _{1} + …+ D_{n}*, and to do it in a way that keeps the number of terms in the sum small.

As we do this, we’ll accumulate a product of rational functions from the div(*u*/*v*) contributions, and in a future post we’ll see how to use that to get a way to evaluate the divisors that we need in pairing-based cryptography.

Exactly how do you find the rational functions *u* and *v*?

Suppose that you have *u*: *y* = *mx* + *b*, or *y* – *mx* – *b* = 0. If that’s the case, you have *u*(*x*, *y*) = *y* – *mx *– *b*.

Suppose that you have *v*: *x* = *c*, or *x* – *c* = 0. If that’s the case, you have *v*(*x*, *y*) = *x* – *c*.

## Tanya Mills

I am currently studying elliptic curves and divisors and always get stuck on this issue of zeros and poles. I’m hoping you might be able to explain something to me. You describe u as the line through through P1, P2 and –P3. I completely understand that those three points are zeros of u, but how do you know that the point at infinity is a pole of order 3? Thanks in advance!

Reply ↓

## Luther Martin

Suppose that we have an elliptic curve y^2 = x^3 + a x + b and a line y = M x + B.

Squaring both sides of the equation for the line gives us y^2 = (M x + B)^2.

So where the line and the curve intersect we have (M x + B)^2 = x^3 + a x + b, which is a cubic in x and has a pole of order 3 at O.

Does that make sense?

Reply ↓

## Tanya Mills

Oh, that is very helpful! I now see how the order could be three, but I’m still stuck on how to show that the point at infinity is a pole? Do you have to homogenize the equation? For example, let E: y^2 = x^3 + 5x defined over F_23. Let f(X, Y) = (y-3x-2)/(x-5) be a rational function on E. I can see that the point at infinity is a pole of f(X, Y) because if I homogenize f(X, Y) and then substitute (0 : 1: 0) for the point at infinity, I get 1/0. Can you do something similar with a linear function to show that the point at infinity is a pole? Or is there another method? Thanks!

Reply ↓

## Luther Martin

The easiest way to see that infinity is a pole of a polynomial might be just straight from the defintion: an analytic function f has a pole of order n at infinity if f(1/z) has a pole of order n at 0.

Reply ↓

## Luther Martin

I’ll also try to answer what’s probably the next reasonable question: why a pole of order 2 from v?

The curve y^2 = x^3 + a x + b intersects the line x = c where y^2 = c^3 + a c + b, which we can write as y^2 = C. In that form it should be clearer that there’s a pole of order 2.

Reply ↓

## Tanya Mills

Wonderful! It is all so clear to me now! Thank you very much! 🙂

Reply ↓