Shorter addition chain for smooth integers using decomposition method.
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 introd...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English English |
| Published: |
Taylor & Francis
2011
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/25154/ http://psasir.upm.edu.my/id/eprint/25154/1/Shorter%20addition%20chain%20for%20smooth%20integers%20using%20decomposition%20method.pdf |
| _version_ | 1848845232027729920 |
|---|---|
| author | Mohamed, M. A. Md. Said, Mohamad Rushdan Mohd Atan, Kamel Ariffin Ahmad Zulkarnain, Zuriati |
| author_facet | Mohamed, M. A. Md. Said, Mohamad Rushdan Mohd Atan, Kamel Ariffin Ahmad Zulkarnain, Zuriati |
| author_sort | Mohamed, M. A. |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-15T08:43:32Z |
| format | Article |
| id | upm-25154 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English English |
| last_indexed | 2025-11-15T08:43:32Z |
| publishDate | 2011 |
| publisher | Taylor & Francis |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-251542015-10-16T07:04:59Z http://psasir.upm.edu.my/id/eprint/25154/ Shorter addition chain for smooth integers using decomposition method. Mohamed, M. A. Md. Said, Mohamad Rushdan Mohd Atan, Kamel Ariffin Ahmad Zulkarnain, Zuriati 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. Taylor & Francis 2011-07 Article PeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/25154/1/Shorter%20addition%20chain%20for%20smooth%20integers%20using%20decomposition%20method.pdf 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 http://www.tandf.co.uk/journals/default.asp 10.1080/00207160.2010.543456 English |
| spellingShingle | Mohamed, M. A. Md. Said, Mohamad Rushdan Mohd Atan, Kamel Ariffin Ahmad Zulkarnain, Zuriati Shorter addition chain for smooth integers using decomposition method. |
| title | Shorter addition chain for smooth integers using decomposition method. |
| title_full | Shorter addition chain for smooth integers using decomposition method. |
| title_fullStr | Shorter addition chain for smooth integers using decomposition method. |
| title_full_unstemmed | Shorter addition chain for smooth integers using decomposition method. |
| title_short | Shorter addition chain for smooth integers using decomposition method. |
| title_sort | shorter addition chain for smooth integers using decomposition method. |
| url | http://psasir.upm.edu.my/id/eprint/25154/ http://psasir.upm.edu.my/id/eprint/25154/ http://psasir.upm.edu.my/id/eprint/25154/ http://psasir.upm.edu.my/id/eprint/25154/1/Shorter%20addition%20chain%20for%20smooth%20integers%20using%20decomposition%20method.pdf |