A hybrid addition chain method for faster scalar multiplication
Solutions to addition chain problem can be applied to operations involving huge number such as scalar multiplication in elliptic curve cryptography. Recently, a decomposition method was introduced, with an intention to generate addition chain with minimal possible terms. Totally different from other...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
World Scientific and Engineering Academy and Society
2015
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/36171/ http://psasir.upm.edu.my/id/eprint/36171/1/A%20Hybrid%20Addition%20Chain%20Method%20For%20Faster%20Scalar%20Multiplication.pdf |
| _version_ | 1848848257917124608 |
|---|---|
| author | Mohamed, Mohamad Afendee Md. Said, Mohamad Rushdan |
| author_facet | Mohamed, Mohamad Afendee Md. Said, Mohamad Rushdan |
| author_sort | Mohamed, Mohamad Afendee |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | Solutions to addition chain problem can be applied to operations involving huge number such as scalar multiplication in elliptic curve cryptography. Recently, a decomposition method was introduced, with an intention to generate addition chain with minimal possible terms. Totally different from others, this new method uses rule representation for prime factors of n, and a new algorithm to generate a complete chain for n. Although the chain is not always optimal, the method is shown to outclass other existing methods for certain cases of n. The method is based on prime power decomposition and it can be seen as a two-layered approach, prime layer and prime power layer. In this paper, we adapt an idea of non-adjacent form into decomposition method at prime layer. This new hybrid method is called signed decomposition method. Our objective is to reduce the number of addition operations for each p by transforming an original unsigned rule into a signed rule. The study shows that the length of this new chain is confined to the same boundary as that of an optimal chain. A series of tests shows that our method outperforms decomposition method as well as earlier methods significantly. Moreover, possible saving of terms can be made more noticeable as we increase the prime factor. |
| first_indexed | 2025-11-15T09:31:38Z |
| format | Article |
| id | upm-36171 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T09:31:38Z |
| publishDate | 2015 |
| publisher | World Scientific and Engineering Academy and Society |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-361712015-09-14T12:20:50Z http://psasir.upm.edu.my/id/eprint/36171/ A hybrid addition chain method for faster scalar multiplication Mohamed, Mohamad Afendee Md. Said, Mohamad Rushdan Solutions to addition chain problem can be applied to operations involving huge number such as scalar multiplication in elliptic curve cryptography. Recently, a decomposition method was introduced, with an intention to generate addition chain with minimal possible terms. Totally different from others, this new method uses rule representation for prime factors of n, and a new algorithm to generate a complete chain for n. Although the chain is not always optimal, the method is shown to outclass other existing methods for certain cases of n. The method is based on prime power decomposition and it can be seen as a two-layered approach, prime layer and prime power layer. In this paper, we adapt an idea of non-adjacent form into decomposition method at prime layer. This new hybrid method is called signed decomposition method. Our objective is to reduce the number of addition operations for each p by transforming an original unsigned rule into a signed rule. The study shows that the length of this new chain is confined to the same boundary as that of an optimal chain. A series of tests shows that our method outperforms decomposition method as well as earlier methods significantly. Moreover, possible saving of terms can be made more noticeable as we increase the prime factor. World Scientific and Engineering Academy and Society 2015 Article PeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/36171/1/A%20Hybrid%20Addition%20Chain%20Method%20For%20Faster%20Scalar%20Multiplication.pdf Mohamed, Mohamad Afendee and Md. Said, Mohamad Rushdan (2015) A hybrid addition chain method for faster scalar multiplication. WSEAS Transactions on Communications, 14. art. no. 19. pp. 144-152. ISSN 1109-2742; ESSN: 2224-2864 http://www.wseas.org/multimedia/journals/communications/2015/a385704-606.pdf |
| spellingShingle | Mohamed, Mohamad Afendee Md. Said, Mohamad Rushdan A hybrid addition chain method for faster scalar multiplication |
| title | A hybrid addition chain method for faster scalar multiplication |
| title_full | A hybrid addition chain method for faster scalar multiplication |
| title_fullStr | A hybrid addition chain method for faster scalar multiplication |
| title_full_unstemmed | A hybrid addition chain method for faster scalar multiplication |
| title_short | A hybrid addition chain method for faster scalar multiplication |
| title_sort | hybrid addition chain method for faster scalar multiplication |
| url | http://psasir.upm.edu.my/id/eprint/36171/ http://psasir.upm.edu.my/id/eprint/36171/ http://psasir.upm.edu.my/id/eprint/36171/1/A%20Hybrid%20Addition%20Chain%20Method%20For%20Faster%20Scalar%20Multiplication.pdf |