A few papers have presented explicit formulas for the doubling and the addition step in Miller's algorithm, but the optimizations were all done for the Tate pairing with degree-$2$ twists, so the main usage of the high-degree twists remained incompatible with more efficient formulas.
In this paper we present efficient formulas for curves with twists of degree $2, 3, 4$ or $6$. These formulas are significantly faster than their predecessors. We show how these faster formulas can be applied to Tate and ate pairing variants, thereby speeding up all practical suggestions for efficient pairing implementations over fields of large characteristic.
Category / Keywords: Pairings, Miller functions, explicit formulas, Tate pairing, ate pairing, twists, Weierstrass curves. Date: received 11 Dec 2009, last revised 14 Jun 2010 Contact author: michael at cryptojedi org Available format(s): PDF | BibTeX Citation Version: 20100614:081650 (All versions of this report) Discussion forum: Show discussion | Start new discussion