The most efficient algorithm for solving the elliptic curve discrete logarithm problem can only be done in exponential time. Hence, we can use it in many cryptographic applications. Weil pairing is a mapping which maps a pair of points on elliptic curves to a multiplicative group of a finite field with nondegeneracy and bilinearity. Pairing was found to reduce the elliptic curve discrete logarithm problem into the discrete logarithm problem of a finite field, and became an important issue since then. In 1986, Miller proposed an efficient algorithm for computing Weil pairings. Many researchers focus on the improvement of this algorithm. In 2006, Blake et al. proposed the reduction of total number of lines based on the conjugate of a line. Liu et al. expanded their concept and proposed two improved methods. In this paper, we use both NAF and segmentation algorithm to implement the Weil pairing and analyse its complexity.

This work introduces fundamental and alternative definition of Weil pairing and proves their equivalence. The alternative definition is more advantageous for the purpose of computing. We assume basic knowledge of elliptic curves in the affine sense. We explain the K-rational maps and its generalization at the point at infinity, rational map. The proof of equivalence of the two mentioned definitions is based upon the Generalized Weil Reciprocity, which uses a concept of local symbol. The text follows two articles from year 1988 and 1990 written by L. Charlap, D. Robbins a R. Coley, and corrects a certain imprecision in their presentation of the alternative definition. Powered by TCPDF (www.tcpdf.org)