On addition-subtraction chains of numbers with low Hamming weight

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
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 |𝓁⁻(2n) − 𝓁⁻(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

1. M. Ciet, M. Joye, K. Lauter,& Montgomery, P. L. (2006). Trading inversions for multiplications in elliptic curve cryptography, Des. Codes Cryptogr., 39, 189–206.
2. Cliff, N. (2011) Shortest addition chains. Available online:
   http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html.
3. 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.
4. Downey, P., Leong, B. & Sethi, R. (1981). Computing sequences with addition chains, SIAM J. Comput., 10, 638–646.
5. Gordon, D.M. (1998). A survey of fast exponentiation methods, Journal of Algorithms, 27, 129–146.
6. Knuth, D. (1969). The Art of Computer Programming, 2nd ed., Addison-Wesley.
7. 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.
8. Le, D. (2011). Fast quadrupling of a point in elliptic curve cryptography, preprint, 2011, Available online: https://eprint.iacr.org/2011/039.
9. Montgomery, P. (1992). Evaluating recurrences of form X_m+n = f(X_m, X_n, X_m−n) via Lucas chains, preprint, 1992, Available online: ftp://ftp.cwi.nl/pub/pmontgom/Lucas.ps.gz.
10. Morain, F. & Olivos, J. (1990). Speeding up the computation on an elliptic curve using addition-subtaction chains, RAIRO Theor. Inform. Appl., 24, 531–543.
11. 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.
12. 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.
13. 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.
14. Volger, H. (1985). Some results on addition/subtraction chains, Inform. Process. Lett., 20, 155–160.
15. Wang, C., Chang, C. & Lin, C. (1999). A method for computing Lucas sequences, Comput. Math. Appl., 38, 187–196.
16. 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.