Divisors

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)

and

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)

and

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.

Leave a Reply

Your email address will not be published. Required fields are marked *