Cover Image

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 oth...

Full description

Saved in:
Bibliographic Details
Main Authors: Mohamad Afendee, Mohamed, Mohamad Rushdan, Md Said
Format: Article
Language:English
Published: 2015
Subjects:
QA Mathematics
QA75 Electronic computers. Computer science
Online Access:http://eprints.unisza.edu.my/5033/1/FH02-FIK-16-04820.pdf
http://eprints.unisza.edu.my/5033/
Tags: Add Tag
No Tags, Be the first to tag this record!
id my-unisza-ir.5033
record_format eprints
spelling my-unisza-ir.50332022-02-03T04:27:44Z http://eprints.unisza.edu.my/5033/ A hybrid addition chain method for faster scalar multiplication Mohamad Afendee, Mohamed Mohamad Rushdan, Md Said QA Mathematics QA75 Electronic computers. Computer science 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. 2015-12 Article PeerReviewed text en http://eprints.unisza.edu.my/5033/1/FH02-FIK-16-04820.pdf Mohamad Afendee, Mohamed and Mohamad Rushdan, Md Said (2015) A hybrid addition chain method for faster scalar multiplication. WSEAS Transactions on Communications, 14 (19). pp. 144-152. ISSN 1109-2742
institution Universiti Sultan Zainal Abidin
building UNISZA Library
collection Institutional Repository
continent Asia
country Malaysia
content_provider Universiti Sultan Zainal Abidin
content_source UNISZA Institutional Repository
url_provider https://eprints.unisza.edu.my/
language English
topic QA Mathematics
QA75 Electronic computers. Computer science
spellingShingle QA Mathematics
QA75 Electronic computers. Computer science
Mohamad Afendee, Mohamed
Mohamad Rushdan, Md Said
A hybrid addition chain method for faster scalar multiplication
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.
format Article
author Mohamad Afendee, Mohamed
Mohamad Rushdan, Md Said
author_facet Mohamad Afendee, Mohamed
Mohamad Rushdan, Md Said
author_sort Mohamad Afendee, Mohamed
title A hybrid addition chain method for faster scalar multiplication
title_short 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_sort hybrid addition chain method for faster scalar multiplication
publishDate 2015
url http://eprints.unisza.edu.my/5033/1/FH02-FIK-16-04820.pdf
http://eprints.unisza.edu.my/5033/
_version_ 1724079416284282880
score 13.211869

Similar Items