TOPICS
Search

Lucas Chain

A Lucas chain for an integer n>=1 is an increasing sequence

1=a_0<a_1<a_2<...<a_r=n

of integers such that every a_k, k>=1, can be written as a sum a_k=a_i+a_j of smaller elements whose difference |a_j-a_i| is also en element of the sequence or zero (i.e., taking i=j is allowed). The number r is called the length of the chain.

For example, 1,2,3,5 is a Lucas chain of length 3 for 5 because 2=1+1, 1-1=0, 3=1+2, 2-1=1, 5=3+2, and 3-2=1. Further examples are sequences of consecutive powers of 2 or the Fibonacci numbers 1, 2, 3, 5, 8, 13, 21, ....

Lucas chains are a special kind of addition chain and can be used to evaluate Lucas functions, which have been proposed for use in public-key cryptography.

See also

Addition Chain, Fibonacci Number, Lucas Sequence

This entry contributed by Martin Kutz

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Kutz, M. "Lower Bounds for Lucas Chains." SIAM J. Comput. 31, 1896-1908, 2002.Montgomery, P. L. "Evaluating Recurrences of Form X_(m+n)=f(X_m,X_n,X_(m-n)) via Lucas Chains." Unpublished manuscript. https://cr.yp.to/bib/1992/montgomery-lucas.pdf.Yen, S.-M. and Laih, C.-S. "Fast Algorithms for LUC Digital Signature Computation." IEE Proc.--Computers and Digital Techn. 142, 165-169, Mar. 1995.

Referenced on Wolfram|Alpha

Lucas Chain

Cite this as:

Kutz, Martin. "Lucas Chain." From MathWorld--A Wolfram Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/LucasChain.html

Subject classifications