A use for equivalent divisors
Two divisors are equivalent if they differ by the divisor of a rational function. When it comes to calculating the pairings that we want to implement for pairing-based cryptography, it can be useful to know when two divisors are equivalent because there are lots of cases where we just need a divisor equivalent to a particular divisor instead just a particular divisor.
If this is the case, then we can pick a divisor that's nice in some way and use it instead of an equivalent but less nice form. In particular, this can help get rid of the point at infinity and use a finite point on an elliptic curve instead. We get Tate pairing of point P of order n and a second point Q, for example, by finding a rational function equivalent to the divisor
n(P) – n(O)
and evaluating this function at a divisor equivalent to
(Q) – (O)
To do this, having a way to get rid of the points at infinity can be useful. Here's a way to do this.
Suppose that we have two divisors on an elliptic curve
D1 = (P1) – (O)
D2 = (P2) – (O)
Let's say that P1 + P2 = P3 and write u as the line through P1, P2 and –P3 and v as the line through P3 and –P3. To help visualize things, the following picture may be useful:
Like we saw in a previous post, we can use u and v to write
(P1) – (O) + (P2) – (O) = (P3) – (O) + div(u/v)
Now let's replace P1 with P, P2 with R and P3 with P + R. With this change of notation we have that
(P) – (O) + (R) – (O) = (P + R) – (O) + div(u/v)
Rearranging terms a bit gives that
[ (P) – (O) ] - [ (P + R) – (R) ] = div(u/v)
or that the divisors
(P) – (O)
(P + R) – (R)
are equivalent because their difference is just div(u/v), which is the divisor of a rational function.
So if we need to do a calculation with a divisor equivalent to (P) – (O), we can just pick a random point R and use the divisor (P + R) – (R) instead of (P) – (O). The point at infinity can make it difficult to do calculations with (P) – (O), but that's not a problem with (P + R) – (R).
There are also other ways to avoid dealing with the point at infinity. Some of these are actually simpler to implement, but they're also a bit more difficult to understand. Maybe that's a topic for a future post.