Faster pairing computation on genus 2 hyperelliptic curves *

摘要

In this paper, new efficient pairings on genus 2 hyperelliptic curves of the form C: y~2 = x~5+ax with embedding degree k satisfying 4|k are constructed, that is an improvement for the results of Fan et al. (2008) [10]. Then a variant of Miller's algorithm is given to compute our pairings. In this algorithm, we just need to evaluate the Miller function at two divisors for each loop iteration. However, Fan et al. had to compute the Miller function at four divisors. Moreover, compared with Fan et al.'s algorithm, the exponentiation calculation is simplified. We finally analyze the computational complexity of our pairings, which shows that our algorithm can save 2036m operations in the base field or be 34.1% faster than Fan et al.'s algorithm. The experimental result shows that our pairing can achieve a better performance.