Open Access Open Access  Restricted Access Subscription Access

Speeding up Simultaneous Scalar Multiplication on Elliptic Curves

manju sanghi


Scalar multiplication is the basic and most expensive operation in elliptic curve based cryptographic protocols.  It is the computation of integer multiple of a given point on the curve.  Computation of scalar multiple is faster by using signed binary representation as compared to binary representation. Direct- recoding is a new and efficient algorithm for computation of signed binary representation as compared to the existing methods like NAF, MOF and complementary recoding. In this paper, we propose a novel method for speeding up simultaneous scalar multiplication using direct recoding method. 

Keywords: Elliptic curve cryptography, simultaneous scalar multiplication, signed binary method, NAF, MOF, complementary recoding, JSF
MSC: 94A60

Full Text:



Diffie, W., Hellman, M.E.: New Directions in Cryptography, IEEE Transactions on

Information Theory, IT-22, 644–654 (1976)

Rivest, R.L., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and

Public-key Cryptosystems. Communications of the ACM 21, 120–126 (1978)

V. S. Miller, Use of elliptic curves in cryptography, Advances in Cryptology, Proceedings of

CRYPTO'85, LNCS, 218 (1986), 417-426.

N. Koblitz, Elliptic curve cryptosystem, Mathematics of Computation, 48 (1987) 203-209.

Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Huanguo

Zhang, Publishing House of Electronics Industry, pp. 74–76 (2005)

Standard Specifications for Public Key Cryptography, IEEE Standard 1363, 2000.

A.D. Booth, A signed binary multiplication technique, Journal of Applied Mathematics, 4(2)

(1951), 236-240.

G. W. Reitwiesner, Binary Arithmetic, Advances in computers, 1 (1960), 231-308.

Gordon, D.M.: A survey of fast exponentiation methods. Journal of Algorithms 27, 129–146


F. Morain, J.Olivos, Speeding up the computations on an elliptic curve using addition

subtraction chains, RAIRO Theoretical Informatics and Applications, 24 (1990), 531-543.

K. Okeya, Signed binary representations revisited, Proceedings of CRYPTO'04 (2004), 123-

M. Joye, S. Yen, Optimal left to right binary signed digit recoding, IEEE Transactions on

Computers, 49 (2000), 740-748.

H.K.Pathak, Manju Sanghi, Speeding up Computation of Scalar Multiplication in

Elliptic Curve Cryptosystem, Journal on computer science and engineering, 2, (2010), 1024-

P.Balasubramaniam, E. Karthikeyan, Fast Simultaneous scalar multiplication, Applied

Mathematics and Computation, 192 (2007), 399-404.

J.A. Solinas, Low-weight binary representations for pairs of integers, Technical Report

CORR 2001-41, Center for Applied Cryptographic Research, University of Waterloo,

Canada, 2001.


  • There are currently no refbacks.