An efficient algorithm for computing the luc chain

Since Lucas functions were introduced for designing public key cryptosystems and digital signatures in cryptography, the question of how to speed up their computation has attracted more attention. The fastest algorithm for computing the Lucas function, that we are aware of, was proposed by Yen and Laih. The authors now propose a more efficient algorithm for computing the Lucas function. It is shown that the length of L(n) needed in the proposed algorithm is only about 1.73t which is less than 2t needed in the Yen-Laih algorithm, where L(.) is the notation of the Lucas chain and / is the bit length of n.