Blog

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

D1 = (P1) – (O)

D2 = (P2) – (O)

Dn = (Pn) – (O)

We can always add the divisors D1 through Dn to get

D = D1 + …+ Dn

= (P1) + … + (Pn) + 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 2160 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 (P1) – (O) + (P2) – (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 P1 and P2 are two points on an elliptic curve and that P3 = P1 + P2. Let u be the line through P1, P2 and –P3, and let v be the line through P3 and –P3.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 P1, P2 and –P3 plus a pole of order 3 at O and v has zeroes at P3 and –P3 plus a pole of order 2 at O. This means that we can write

div(u) = (P1) + (P2) + (–P3) – 3(O)

and

div(v) = (P3) + (–P3) – 2(O)

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

div(u) – div(v) = (P1) + (P2) + (–P3) – 3(O) – ((P3) + (–P3) – 2(O))

= (P1) + (P2) – (P3) – (O)

= [(P1) – (O)] + [(P2) – (O)] – [(P3) – (O)]

or that

[(P1) – (O)] + [(P2) – (O)] = (P3) – (O) + div(u/v)

So if D1 = (P1) – (O) and D2 = (P2) – (O), this gives us a way to find D1 + D2 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 = D1 + …+ Dn, 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 ymxb = 0. If that’s the case, you have u(x, y) = ymx b.

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

• 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!

• 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?

• 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!

• 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.

• 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.

• Tanya Mills

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