Moody, D.
and Tall, A.
(2019),
On addition-subtraction chains of numbers with low Hamming weight, Notes on Number Theory and Discrete Mathematics, [online], https://doi.org/10.7546/nntdm.2019.25.2.155-168 (Accessed May 13, 2026)
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
On addition-subtraction chains of numbers with low Hamming weight
Published
Author(s)
, Amadou Tall
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 addition-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-subtraction as a tool to construct such minimal chains. Specifically, if we let l(n) stand for the minimal length of all the Lucas addition-subtraction chains for n, we prove |l(2n)-l(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.Citation
Notes on Number Theory and Discrete Mathematics
Volume
25
Issue
2
Pub Type
Journals
Download Paper
Keywords
addition chains, subtraction chains, addition-subtraction chains, Lucas chains
Citation
Issues
If you have any questions about this publication or are having problems accessing it, please contact [email protected].
Created July 1, 2019, Updated July 15, 2019