ABSTRACT

In this chapter, the author reviews several techniques that will allow students to greatly reduce the computational cost of the final exponentiation step. The computation of the final exponentiation can be highly optimized by taking advantage of the definition of the embedding degree k. By far the most popular cryptographic instantiation of a bilinear pairing is the Tate pairing or variants of it. After having processed all the elements in the addition chain, the vectorial addition chain is obtained by scanning the columns in the Olivos array from right to left. Moreover, the underlined rows and all repeated columns are ignored.