TWO FAST ALGORITHMS FOR COMPUTING POINT SCALAR MULTIPLICATIONS ON ELLIPTIC CURVES

The key operation in Elliptic Curve Cryptosystems(ECC) is point scalar multiplication. Making use of Frobenius endomorphism, Muller and Smart proposed two efficient algorithms for point scalar multiplications over even or odd finite fields respectively. This paper reduces the corresponding multiplier by modulo Υk-1 +…+Υ+ 1 and improves the above algorithms. Implementation of our Algorithm 1 in Maple for a given elliptic curve shows that it is at least as twice fast as binary method. By setting up a precomputation table, Algorithm 2, an improved version of Algorithm 1, is proposed. Since the time for the precomputation table can be considered free, Algorithm 2 is about (3/2) log2 q - 1 times faster than binary method for an elliptic curve over

The key operation in Elliptic Curve Cryptosystems(ECC) is point scalar multiplication. Making use of Frobenius endomorphism, Miiller and Smart proposed two efficient algorithms for point scalar multiplications over even or odd finite fields respectively. This paper reduces thementation of our Algorithm 1 in Maple for a given elliptic curve shows that it is at least as twice fast as binary method. By setting up a precomputation table, Algorithm 2, an improved version of Algorithm 1, is proposed. Since the time for the precomputation table can be considered free,Algorithm 2 is about (3/2) log2 q - 1 times faster than binary method for an elliptic curve over Fq.