UPM Institutional Repository

Shorter addition chain for smooth integers using decomposition method.


Mohamed, M. A. and Md. Said, Mohamad Rushdan and Mohd Atan, Kamel Ariffin and Ahmad Zulkarnain, Zuriati (2011) Shorter addition chain for smooth integers using decomposition method. International Journal of Computer Mathematics , 88 (11). pp. 2222-2232. ISSN 0020-7160


An efficient computation of scalar multiplication in elliptic curve cryptography can be achieved by reducing the original problem into a chain of additions and doublings. Finding the shortest addition chain is an NP-problem. To produce the nearest possible shortest chain, various methods were introduced and most of them depends on the representation of a positive integer n into a binary form. Our method works out the given n by twice decomposition, first into its prime powers and second, for each prime into a series of 2's from which a set of rules based on addition and doubling is defined. Since prime factorization is computationally a hard problem, this method is only suitable for smooth integers. As an alternative, the need to decompose n can be avoided by choosing n of the form p1 e1p2 e2⋯r er. This shall not compromise the security of ECC since its does not depend on prime factorization problem. The result shows a significant improvement over existing methods especially when n grows very large.

Download File

PDF (Abstract)
Shorter addition chain for smooth integers using decomposition method.pdf

Download (193kB) | Preview
Official URL or Download Paper: http://www.tandf.co.uk/journals/default.asp

Additional Metadata

Item Type: Article
Divisions: Faculty of Science
DOI Number: https://doi.org/10.1080/00207160.2010.543456
Publisher: Taylor & Francis
Keywords: Elliptic curves cryptography; Addition chain; Scalar multiplication; Binary method; Non-adjacent form; Complementary recoding.
Depositing User: Nur Farahin Ramli
Date Deposited: 17 Jul 2013 08:24
Last Modified: 16 Oct 2015 07:04
Altmetrics: http://www.altmetric.com/details.php?domain=psasir.upm.edu.my&doi=10.1080/00207160.2010.543456
URI: http://psasir.upm.edu.my/id/eprint/25154
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item