A method for computing Lucas sequences
Most of public-key cryptosystems rely on one-way functions, which can be used to encrypt and sign messages, Their encryption and signature operations are based on the computation of exponentiation. Recently, some public-key cryptosystems are proposed and based on Lucas functions, and the Lucas sequences are performed as S = V(d)modN. In this paper, we will transform the concept of addition chains for computing the exponentiation evaluations to the Lucas chains for computing the Lucas sequences. Theoretically, the shorter Lucas chain for d is generated, the less computation time for evaluating the value V(d) is required. Therefore, we proposed a heuristic algorithm for evaluating a shorter Lucas chain and then use it to compute the Lucas sequence with less modular multiplications. (C) 1999 Elsevier Science Ltd. All rights reserved.
cryptosystem addition chain lucas chain signature scheme