Certain functions called pairings are an important part of the mathematical machinery that make pairing-based cryptographic algorithms possible. Pairings, in turn, are based on the idea of a divisor. These divisors aren’t those you see in elementary number theory, where 4 is a divisor of 12, for example. Instead, they’re a way of keeping track of the zeroes and poles of a rational function.
The zeroes and poles of a rational function define the rational function up to multiplication by a constant. So if we know that we have a rational function with a zero of order two at x = 1 and a pole of order one at x = 2, then the function has to look like
f(x) = c (x – 1)2 / (x – 2)
A divisor is a way to keep track of the zeroes and poles of a rational function by using a notation that looks much like addition of integers. We write the divisor of f as
div(f) = 2(1) – (2) – (¥)
What’s in the parentheses tells us where we have a zero or pole and the coefficient in front of the parentheses tells us the order of the zero or pole. Positive numbers indicate a zero; negative numbers indicate a pole. Note that this particular rational function also has a pole at x = ¥, and the divisor that we write for it reflects this.
So if we write
div(f1) = (3) – (¥)
that tells us that f1is a rational function with a zero at x = 3 and a pole at x = ¥, so that, up to a constant factor, f1 looks like
f1(x) = x – 3
We can add divisors by adding the coefficients of like terms, so that if
div(g) = (3) – 2(1) + (¥)
which corresponds to
g(x) = (x – 3) / (x – 1)2
then we can add div(f) and div(g) to get
div(f) + div(g) = 2(1) – (2) – (¥) + (3) – 2(1) + (¥)
= (3) – (2)
which corresponds to the rational function
h(x) = (x – 3) / (x – 2)
Clearly, adding divisors corresponds to multiplying rational functions, and if we define subtraction in the natural way, it corresponds to dividing rational functions. So we can write
div(f) + div(g) = div(fg)
div(f) – div(g) = div(f/g).
Note that the divisor div(1) acts much like 0 does in the integers. In the integers, adding or subtracting 0 doesn't change the value of an integer. The divisor div(1) behaves the same way:
div(f) + div(1) = div(f)
div(f) - div(1) = div(f)
The notation for divisors isn’t quite the same as addition, because we can’t simplify divisors by reducing (1) – (1) to div(1), for example.
Tomorrow: divisors on elliptic curves.