Lucas/Differential Addition Chains

For mathematical definitions see the top-level Addition Chains.

Lucas or Differential addition chains appeared in an unpublished work [1].
If we look at the standard addition chain \(1=a_0<a_1<...<a_r=n, a_i=a_j+a_k,0\le k\le j<i\le r\) then Lucas chains have the additional requirement that \(a_j-a_k=0\) or \(a_j-a_k=a_d, 0\le d<j\).
We say this addition chains has length \(r\) and denote by \(L(n)=r\) the smallest Lucas chain for \(n\).
This extra condition forces either a Lucas chain to contain only one doubling step (1, 2) or it consists of multiple smaller addition chains combined in what's called the factor method.
For example, we combine the addition chain \(a_0<a_1<...<a_r=n\) with the addition chain \(b_0<b_1<...<b_s=m\) to form the addition chain \(a_0<a_1<...<a_r=a_r\cdot b_0<a_r\cdot b_1<...<a_r\cdot b_s=n\cdot m\).
So, we get an addition chain of length \(r+s\) for \(n\cdot m\). Hence \(L(n\cdot m)\le L(m)+L(n)\).

A strategy then for searching for optimal (shortest) Lucas chains then is to start by finding all chains of length 0 (only 1). Then given a database of all \(n\) with \(L(n)=r\) first find all \(L(n)=r+1\) via the factor method then search for addition chains that contain only 1 doubling step.
In [2] the authors suggest a Fibonacci bound of \(a_i\ge \lceil {n\over{F_{r-i+2}}}\rceil\) (where \(F_i\) is the i'th Fibonacci number) for chains with only one doubling step. It's easy to see that if \(i>0\) then \(a_i\ge \lceil {n-F_{r-i+1}\over{F_{r-i+2}}}\rceil +1\) since the single doubling step is not used. This only increase the bound by 1 at most. I have code that uses Integer Programming (IP) to automatically find bounds of addition chains by enumerating all chain ends. I have not thought of a way of encoding the difference of the sums into this.
I hacked up the NMC program described here Finding \(\Lambda\) Values to find Lucas chains. The Fibonacci bounds were very effective, and I was able to calculate all \(L(n)\) values for \(n\le 2^{33}\).
In his thesis [3] Bleichenbacher seems to have calculated all \(L(n)\) for \(n\le 432199\) and recorded \(C_L(r)\) (Smallest number with an optimal Lucas chain of length \(n\)). This result appears on OEIS A104892.

The data for \(L(n)\) values for \(n\le 2^{33}\) can be found here: addl33.bin.gz
It's a simple byte per value index at zero. So, ignore the first byte as that is only there as I like to map these files into memory and it's convenient if they start at zero.

My initial attempt at enumerating all chains with \(n\le 2^{32}\) suffered from a pruning bug. Overflow in all 16 32-bit slots made the algorithm quit searching at the last level. You can quit if all values are smaller than the bounds, but overflow has to be handled. I shifted to using 8 64-bit integers backing into the 512-bit SIMD registers.
 

[1] Montgomery, Peter L. "Evaluating recurrences of form." Xm+n= f (Xm, Xn, Xm− n) (1992).
[2] Bernstein, Daniel J., Jolijn Cottaar, and Tanja Lange. "Searching for differential addition chains." Cryptology ePrint Archive (2024).
[3] Bleichenbacher, Daniel. Efficiency and security of cryptosystems based on number theory. Diss. ETH Zurich, 1996.