ABSTRACT
Pairing computations will rely crucially on evaluating functions on points of elliptic curves. A convenient way to represent functions is by their divisor. Miller’s basic algorithm described is an extension of the double-and-add method for finding a point multiple. With the inception of pairing-based protocols in the early 2000s, the cryptographic community put in a lot of effort in simplifying and optimizing this algorithm. The complexity of Miller’s algorithm heavily depends on the length of the Miller loop. Major progress in pairing computation was made in 2006, with the introduction of the loop-shortening technique.
