A method for computing Lucas sequences

✍ Scribed by Ching-Te Wang; Chin-Chen Chang; Chu-Hsing Lin

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 635 KB
• Volume: 38
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/s0898-1221(99)00297-7

✦ Synopsis

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. (~) 1999 Elsevier Science Ltd. All rights reserved.