Cryptology ePrint Archive: Report 2004/065

Refinements of Miller's Algorithm for Computing Weil/Tate Pairing

Ian Blake, Kumar Murty, and Guangwu Xu

Abstract: In this paper we propose three refinements to Miller's algorithm for computing Weil/Tate Pairing.The first one is an overall improvement and achieves its optimal behavior if the binary expansion of the involved integer has more zeros. If more ones are presented in the binary expansion, second improvement is suggested. The third one is especially efficient in the case base three. We also have some performance analysis.

Category / Keywords: foundations / algorithm, elliptic curve, cryptography, Weil/Tate pairing

Date: received 27 Feb 2004

Contact author: gxu at comm utoronto ca

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20040229:085920 (All versions of this report)

Short URL: ia.cr/2004/065

Discussion forum: Show discussion | Start new discussion