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.