Cryptology ePrint Archive: Report 2007/311

A Refined Algorithm for the $\eta_T$ Pairing Calculation in Characteristic Three

Jean-Luc Beuchat and Masaaki Shirase and Tsuyoshi Takagi and Eiji Okamoto

Abstract: We describe further improvements of the $\eta_T$ pairing algorithm in characteristic three. Our approach combines the loop unrolling technique introduced by Granger {\em et. al} for the Duursma-Lee algorithm, and a novel algorithm for multiplication over $\mathbb{F}_{3^{6m}}$ proposed by Gorla {\em et al.} at SAC 2007. For $m=97$, the refined algorithm reduces the number of multiplications over $\mathbb{F}_{3^m}$ from $815$ to $692$.

Category / Keywords: implementation / $\eta_T$ pairing, finite field arithmetic, characteristic three

Date: received 10 Aug 2007, last revised 21 Aug 2007

Contact author: beuchat at risk tsukuba ac jp

Available format(s): PDF | BibTeX Citation

Version: 20070821:082211 (All versions of this report)

Short URL: ia.cr/2007/311

Discussion forum: Show discussion | Start new discussion