Getting a rational function from n(P) – n(O)
In a previous post we saw how to add divisors like (P1) – (O) and (P2) – (O) and reduce the sum to the form (Q) – (O). Suppose that P is a point of order n and see what happens when we use this approach to evaluate
n(P) – n(O) = (P) – (O) + …+ (P) – (O)
We can do this by first finding
(P) – (O) + (P) – (O) = (2P) – (O) + div(f1)
where we’ve written f1 = u1 / v1 where u1 is the line through P and P, and v1 is the vertical line through 2P and -2P.
Next, we can find
3((P) – (O)) = (P) – (O) + (2P) – (O) + div(f1)
= (3P) – (O) + div(f1f2)
where we’ve written f2 = u2 / v2 where u2 is the line through P and 2P and v2 is the vertical line through 3P and -3P.
We can continue this process until we get to
n((P) – (O)) = (nP) – (O) + div(f1…fn-1)
= (O) – (O) + div(f1…fn-1)
Note that by doing this, we’ve found a way to write n(P) – n(O) as the divisor of the rational function fP = f1…fn-1. To calculate the pairings that we need for pairing-based cryptographic algorithms, we want to evaluate fP, and we can get this fP through the process that’s described above. That’s almost enough to define how to evaluate the Tate pairing. The rest of what’s needed will be the topic of tomorrow’s post.