An Improved Scalar-Multiplication Algorithm in Galois Field

Studies scalar multiplication algorithms to speed up the elliptic curve cryptosystem. By analyzing features of scalar multiplication, it is found that reducing the number of elliptic operations can lead to a marked speeding up scalar multiplication. For the base point’s scalar multiplication, an important scalar multiplication, the signed window method is improved, and the power table method is designed, to reduce the number of elliptic operations. On the PC, compared to a system with the 4 width signed window method, the speed of a 113 bit EC ElGamal cryptosystem is improved 1/3. Power table method improves the base point’s scalar multiplication, by using the principle of signed window method. With analysis and experiments, it is proved that pwoer table method can remarkably speed up encoding of EC ElGamal cryptosystem.