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)
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)]
[(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 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.