A Variant of Miller Formula and Algorithm
Published in Pairing-Based Cryptography, 2010
Recommended citation: John Boxall, Nadia El Mrabet, Fabien Laguillaumie, Duc-Phong Le. " A variant of Miller formula and algorithm (2010)." Pairing 2010. https://link.springer.com/chapter/10.1007/978-3-642-17455-1_26
Miller’s algorithm is at the heart of all pairing-based cryptosystems since it is used in the computation of pairing such as that of Weil or Tate and their variants. Most of the optimizations of this algorithm involve elliptic curves of particular forms, or curves with even embedding degree, or having an equation of a special form. Other improvements involve a reduction of the number of iterations.
In this article, we propose a variant of Miller’s formula which gives rise to a generically faster algorithm for any pairing friendly curve. Concretely, it provides an improvement in cases little studied until now, in particular when denominator elimination is not available. It allows for instance the use of elliptic curve with embedding degree not of the form $2^i3^j$, and is suitable for the computation of optimal pairings. We also present a version with denominator elimination for even embedding degree. In our implementations, our variant saves between $10\%$ and $40\%$ in running time in comparison with the usual version of Miller’s algorithm without any optimization.
Recommended citation: John Boxall, Nadia El Mrabet, Fabien Laguillaumie, Duc-Phong Le. (2010). A variant of Miller’s formula and algorithm. Pairing-Based Cryptography 2010.