Fast Scalar Multiplication for Elliptic Curves over Binary Fields by Efficiently Computable Formulas

摘要

This paper considers efficient scalar multiplication of elliptic curves over binary fields with a twofold purpose. Firstly, we derive the most efficient 3P formula in A-projective coordinates and 5P formula in both affine and A-projective coordinates. Secondly, extensive experiments have been conducted to test various multi-base scalar multiplication methods (e.g., greedy, ternary/binary, multi-base NAF, and tree-based) by integrating our fast formulas. The experiments show that our 3P and 5P formulas had an important role in speeding up the greedy, the ternary/binary, the multi-base NAF, and the tree-based methods over the NAF method. We also establish an efficient 3P formula for Koblitz curves and use it to construct an improved set for the optimal pre-computation of window TNAF.