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
- end
- end
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 .