Improved Algorithms for Elliptic Curve Arithmetic in GF(2n)

This paper describes three contributions for efficient implementation of elliptic curve cryptosystems in GF(2n). The first is a new method for doubling an elliptic curve point, which is simpler to implement than the fastest known method, due to Schroeppel, and which favors sparse elliptic curve coefficients. The second is a generalized and improved version of the Guajardo and Paar’s formulas for computing repeated doubling points. The third contribution consists of a new kind of projective coordinates that provides the fastest known arithmetic on elliptic curves. The algorithms resulting from this new formulation lead to a running time improvement for computing a scalar multiplication of about 17% over previous projective coordinate methods.