**Analyzing the Galbraith-Lin-Scott Point Multiplication Method for Elliptic Curves over Binary Fields**

*Darrel Hankerson and Koray Karabina and Alfred Menezes*

**Abstract: **Galbraith, Lin and Scott recently constructed efficiently-computable
endomorphisms for a large family of elliptic curves defined over
F_{q^2} and showed, in the case where q is prime, that the
Gallant-Lambert-Vanstone point multiplication method for these curves
is significantly faster than point multiplication for general elliptic
curves over prime fields. In this paper, we investigate the potential
benefits of using Galbraith-Lin-Scott elliptic curves in the case
where q is a power of 2. The analysis differs from the q prime case
because of several factors, including the availability of the point
halving strategy for elliptic curves over binary fields. Our analysis
and implementations show that Galbraith-Lin-Scott offers significant
acceleration for curves over binary fields, in both doubling- and
halving-based approaches. Experimentally, the acceleration surpasses
that reported for prime fields (for the platform in common), a
somewhat counterintuitive result given the relative costs of point
addition and doubling in each case.

**Category / Keywords: **public-key cryptography / elliptic curve, point multiplication, GLV method, isogeny

**Date: **received 1 Aug 2008, last revised 7 Oct 2008

**Contact author: **hankedr at auburn edu

**Available format(s): **PDF | BibTeX Citation

**Note: **Minor revision; updated data from eprint 2008/194.

**Version: **20081007:200349 (All versions of this report)

**Short URL: **ia.cr/2008/334

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]