Efficient point multiplication for elliptic curves over special optimal extension fields
type: Item
instance of: scholarly article
zbMATH Open document ID: 1019.11037
author: Volker Müller
publication date: 2003-06-24T00:00:00Z
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 14Q05
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 1693635
zbMATH Keywords: elliptic curve
zbMATH Keywords: fast multiplication
zbMATH Keywords: efficient endomorphism
MaRDI profile type: Publication
title: Efficient point multiplication for elliptic curves over special optimal extension fields
review text: \textit{R. P. Gallant, R. J. Lambert} and \textit{S. A. Vanstone} [Faster point multiplication on elliptic curves with efficient endomorphisms (2001; Zbl 1002.94022)] have developed an algorithm for fast multiplication of points on elliptic curves over finite fields, based on the existence of efficient endomorphisms. Basically, the idea for computing \(kP\) for a certain point \(P\) of order \(n\) and a certain integer \(0<k<n\) is to look for expansions: \(kP=k_0P+k_1\psi(P)\), where \(k_0,k_1\) are integers of size approximately \(\sqrt n\) and \(\psi\) is an endomorphism of the elliptic curve whose evaluation is sufficiently fast. This expression can then be evaluated with parallel point multiplication techniques. NEWLINENEWLINENEWLINEIn the paper under review these ideas are generalized to expansions involving higher powers of \(\psi\). To this end some variants of simultaneous multiple point multiplication algorithms are worked out. The suitable scenario for this generalization to be of practical use are the optimal extension fields introduced by Bailey and Paar, which are fields generated by irreducible polynomials of the form \(X^r-m\) over a prime field \(\mathbb{F}_p\), with \(p=2^t-s\), \(t=31,32\) and \(s\) small. The paper presents computations for some elliptic curves defined over \(\mathbb{F}_p\) such that the group of points \(E(\mathbb{F}_{p^7})\) has cryptographic relevance and the Frobenius endomorphism leads to expansions of length 7 where the method works efficiently. Due to the efficient implementation of the field arithmetic for optimal extension fields, this multiplication algorithm makes these curves good candidates for fast software implementation of elliptic curve cryptography on 32-bit computers.NEWLINENEWLINEFor the entire collection see [Zbl 0976.00054].
reviewed by: Enric Nart
description: scientific article; zbMATH DE number 1693635