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₁ = (P₁) – (O)

D₂ = (P₂) – (O)

…

D_n = (P_n) – (O)

We can always add the divisors D₁ through D_n to get

D = D₁ + …+ D_n

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

div(u) = (P₁) + (P₂) + (–P₃) – 3(O)

and

div(v) = (P₃) + (–P₃) – 2(O)

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

div(u) – div(v) = (P₁) + (P₂) + (–P₃) – 3(O) – ((P₃) + (–P₃) – 2(O))

= (P₁) + (P₂) – (P₃) – (O)

= [(P₁) – (O)] + [(P₂) – (O)] – [(P₃) - (O)]

or that

[(P₁) – (O)] + [(P₂) – (O)] = (P₃) - (O) + div(u/v)

So if D₁ = (P₁) – (O) and D₂ = (P₂) – (O), this gives us a way to find D₁ + D₂ 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₁ + …+ 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.

Comments

[Tanya Mills]

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

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

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

[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]

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]

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!