Implementing cryptographic pairings
Here we review the state of the art in cryptographic pairing implementation. Starting with a basic Miller algorithm for the Tate pairing we show how to successively apply a series of optimizations and tricks to improve performance. We will concentrate on the case of nonsupersingular prime characteristic elliptic curves, although many of the optimizations equally apply to the cases of supersingular elliptic and hyperelliptic curves. We also discuss optimal implementation of extension field arithmetic.