Dustin Moody and Amadou Tall

Notes on Number Theory and Discrete Mathematics

Print ISSN 1310–5132, Online ISSN 2367–8275

Volume 25, 2019, Number 2, Pages 155-168

DOI: 10.7546/nntdm.2019.25.2.155-168

**Download full paper: PDF, 200 Kb**

## Details

### Authors and affiliations

Dustin Moody

*Computer Security Division, National Institute of Standards and Technology
Gaithersburg, Maryland, 20899, USA
*

Amadou Tall

*Departement de Mathematiques et Informatique,
Universite Cheikh Anta Diop de Dakar, Dakar, Senegal*

### Abstract

An addition chain is a sequence of integers such that every element in the sequence is the sum of two previous elements. They have been much studied, and generalized to additions-subtraction chains, Lucas chains, and Lucas addition-subtraction chains. These various chains have been useful in finding efficient exponentiation algorithms in groups. As a consequence, finding chains of minimal length is critical. The main objective of this paper is to extend results known for addition chains to addition-subtraction chains with Lucas addition-subraction as a tool to construct such minimal chains. Specifically, if we let 𝓁^{−}(*n*) stand for the minimal length of all the Lucas addition-subtraction chains for *n*, we prove |𝓁^{−}(2*n*) − 𝓁^{−}(*n*)| ≤ 1 for all integers *n* of Hamming weight ≤ 4. Thus, to find a minimal addition-subtraction chains for low Hamming weight integers, it suffices to only consider odd integers.

### Keywords

- Addition chains
- Subtraction chains
- Addition-subtraction chains
- Lucas chains

### 2010 Mathematics Subject Classification

- 05A18

### References

- M. Ciet, M. Joye, K. Lauter,& Montgomery, P. L. (2006). Trading inversions for multiplications in elliptic curve cryptography, Des. Codes Cryptogr., 39, 189–206.
- Cliff, N. (2011) Shortest addition chains. Available online:

http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html. - Dimitrov, V., Imbert, L. & Mishra, P. K. (2005). Efficient and secure elliptic curve point multiplication using double-base chains, in Advances in Cryptology – ASIACRYPT 2005, Lect. Notes in Comp. Sci., 3788, Springer-Verlag, 59–78.
- Downey, P., Leong, B. & Sethi, R. (1981). Computing sequences with addition chains, SIAM J. Comput., 10, 638–646.
- Gordon, D.M. (1998). A survey of fast exponentiation methods, Journal of Algorithms, 27, 129–146.
- Knuth, D. (1969). The Art of Computer Programming, 2nd ed., Addison-Wesley.
- Koyama, K. & Tsuruoka, Y. (1993). Speeding elliptic cryptosystems using a signed binary window method, in Advances in Cryptology – CRYPTO 1993, Lect. Notes in Comput. Sci. 740, Springer-Verlag, 345–357.
- Le, D. (2011). Fast quadrupling of a point in elliptic curve cryptography, preprint, 2011, Available online: https://eprint.iacr.org/2011/039.
- Montgomery, P. (1992). Evaluating recurrences of form
*X*_{m+n}=*f*(*X*,_{m}*X*,_{n}*X*) via Lucas chains, preprint, 1992, Available online: ftp://ftp.cwi.nl/pub/pmontgom/Lucas.ps.gz._{m−n} - Morain, F. & Olivos, J. (1990). Speeding up the computation on an elliptic curve using addition-subtaction chains, RAIRO Theor. Inform. Appl., 24, 531–543.
- Sakai, Y. & Sakurai, K. (2001). Efficient scalar multiplication on elliptic curve with direct computations of several doublings, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 84, 120–129.
- Takagi, T., Reis, D., Yen, S. & Wu, B. (2006). Radix-r non-adjacent form and its application to pairing-based cryptosystem, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 89, 115–123.
- Tall, A. (2013). A generalization of Lucas addition chains, Bull. Math. Soc. Sci. Math. Roumanie 55, 1. Available online: https://eprint.iacr.org/2011/378.pdf.
- Volger, H. (1985). Some results on addition/subtraction chains, Inform. Process. Lett., 20, 155–160.
- Wang, C., Chang, C. & Lin, C. (1999). A method for computing Lucas sequences, Comput. Math. Appl., 38, 187–196.
- Yacobi, Y. (1991). Exponentiating faster with addition chains, In: Advances in Cryptology – EUROCRYPT 1990 Lect. Notes in Comput. Sci., Vol. 473, Springer-Verlag, 222–229.

## Related papers

## Cite this paper

APAMoody, D. & Tall, A. (2019). On addition-subtraction chains of numbers with low Hamming weight. Notes on Number Theory and Discrete Mathematics, 25(2), 155-168, doi: 10.7546/nntdm.2019.25.2.155-168.

ChicagoMoody, D. and A. Tall. “On addition-subtraction chains of numbers with low Hamming weight.” Notes on Number Theory and Discrete Mathematics 25, no. 2 (2019): 155-168, doi: 10.7546/nntdm.2019.25.2.155-168.

MLAMoody, D. and A. Tall. “On addition-subtraction chains of numbers with low Hamming weight.” Notes on Number Theory and Discrete Mathematics 25.2 (2019): 155-168. Print, doi: 10.7546/nntdm.2019.25.2.155-168.