In 1986 Victor Miller described an algorithm for computing the Weil pairing
in his unpublished manuscript. This algorithm has then become the core of all
pairing-based cryptosystems. Many improvements of the algorithm have been
presented. Most of them involve a choice of elliptic curves of a \emph{special}
forms to exploit a possible twist during Tate pairing computation. Other
improvements involve a reduction of the number of iterations in the Miller's
algorithm. For the generic case, Blake, Murty and Xu proposed three refinements
to Miller's algorithm over Weierstrass curves.