Fast Multiplication on Elliptic Curves Over GF(2m) without precomputation

This paper describes an algorithm for computing elliptic scalar multiplications on non-supersingular elliptic curves defined over GF(2m). The algorithm is an optimized version of a method described in [1], which is based on Montgomery’s method [8]. Our algorithm is easy to implement in both hardware and software, works for any elliptic curve over GF(2m), requires no precomputed multiples of a point, and is faster on average than the addition-subtraction method described in draft standard IEEE P1363. In addition, the method requires less memory than projective schemes and the amount of computation needed for a scalar multiplication is fixed for all multipliers of the same binary length. Therefore, the improved method possesses many desirable features for implementing elliptic curves in restricted environments.