Lucas chain

In mathematics, a Lucas chain is a restricted type of addition chain, named for the French mathematician Édouard Lucas. It is a sequence

${\displaystyle a_{0},a_{1},a_{2},a_{3},\ldots }$

that satisfies a₀=1, and, for each k > 0,

${\displaystyle a_{k}=a_{i}+a_{j},}$

and either

${\displaystyle a_{i}=a_{j}{\text{ or }}\vert a_{i}-a_{j}\vert =a_{m}}$

for some i, j, m < k.

The sequence of powers of 2 (1, 2, 4, 8, 16, ...) and the Fibonacci sequence (with a slight adjustment of the starting point 1, 2, 3, 5, 8, ...) are simple examples of Lucas chains.

Lucas chains were introduced by Peter Montgomery in 1983. They are analogous to addition chains, in that just as an addition chain A that ends with n allows for evaluating aⁿ in len(A) steps, a Lucas chain C that ends with n allow for evaluating the Lucas sequence terms {U, V }_n (P, Q) in len(C) steps.

Just like the addition chain, a basic method for computing a Lucas chain that ends with n is via the binary method, similar to exponentiation by squaring. This gives a chain length of O(log n). Shorter chains can be obtained using a range of other methods such as Montgomery's PRAC. Because the process of finding a better chain is expensive, good chains are usually precomputed. DJ Bernstein mentions a number of Lucas chain-based schemes in 2017.^: §4.8.2

If L(n) is the length of the shortest Lucas chain for n, then Kutz has shown that most n do not have L < (1-ε) log_φ(n), where φ is the Golden ratio.

References

• Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. pp. 169–171. ISBN 978-0-387-20860-2. Zbl 1058.11001.
• Kutz, Martin (2002). "Lower Bounds For Lucas Chains" (PDF). SIAM J. Comput. 31 (6): 1896–1908. doi:10.1137/s0097539700379255. Zbl 1055.11077.
• Montgomery, Peter L. (1983). "Evaluating Recurrences of Form X_m+n = f(X_m, X_n, X_m-n) Via Lucas Chains" (PS). Unpublished.