Affiliations: [a] Institute of Mathematics and Cryptology, Military University of Technology, Kaliskiego 2, 00-908 Warsaw, Poland. michal.wronski@wat.edu.pl | [b] Warsaw School of Economics, Aleja Niepodległości 162, 02-554 Warszawa, Poland. rdrylo@sgh.waw.pl | [c] Institute of Mathematics and Cryptology, Military University of Technology, Kaliskiego 2, 00-908 Warsaw, Poland. tomasz.kijko@wat.edu.pl | [d] Institute of Mathematics and Cryptology, Military University of Technology, Kaliskiego 2, 00-908 Warsaw, Poland. piotr.bora@wat.edu.pl
Correspondence:
[*]
Address for correspondece: Military University of Technology in Warsaw, Kaliskiego 2 , 00-908 Warsaw, Poland.
Abstract: The GLV method allows to improve scalar multiplication on an elliptic curve E/𝔽q with an efficiently computable endomorphism Φ : E → E over 𝔽q. For points in a subgroup of large prime order r this requires decomposition of scalar k = k0 + k1λ mod r, where Φ acts on the subgroup of order r as multiplication by λ ∈ 𝔽r and k0, k1 are integers O(r)
. In this note we consider the case when λ is of the form λ = 2s + a, where a is a small integer and λ=O(r), which allows very easy and fast decomposition of k especially in hardware implementations. We give a method to construct such elliptic curves based on the complex multiplication method, and give examples of elliptic curves for λ ∈ {2s, 2s − 1} and various security levels.
