Computing the Tate Pairing
Suppose we are working on a curve over with security multiplier such that is contained in .
where is a divisor equivalent to . and . For a supersingular curve with , we may simplify this to provided .
Miller’s Algorithm
Let be the line between the points and , and let be the function with divisor . Then for all , we have . Let the binary representation of be . Then Miller’s algorithm is the following:
-
set and
-
for to 0 do
-
set and
-
if then set and
-
At the end, , and .
Note on implementation: by adding extra logic in the above algorithm, one can avoid handling points of infinity when computing the functions.
The functions
Let the curve be .
-
Tangents: At the point , the line describing the tangent at that point is , where .
-
Vertical lines: These are lines between and . Let . Then the vertical line through is .
-
Other lines: The line between and is given by where .
In implementations, it may be more efficient scale appropriately and do all the divisions at once.