Int. J. Communications, Network and System Sciences, 2010, 3, 943-944
doi:10.4236/ijcns.2010.312128 Published Online December 2010 (http://www.SciRP.org/journal/ijcns)
On Lucas Sequences Computation
Aleksey Koval
Computer Science Department, New Jersey Institute of Technology, Newark, USA
Received September 28, 2010; revised October 29, 201 0; accepted November 21, 2010
Abstract
This paper introduces an improvement to a currently published algorithm to compute both Lucas “sister” se-
quences Vk and Uk. The proposed algorithm uses Lucas sequence properties to improve the running time by
about 20% over the algorithm published in [1].
Keywords: Lucas Sequences, Cryptography
1. Introduction
Lucas sequences have been used extensively in the field
of cryptography. Two cryptosystems based on DLP for
Lucas sequences LUCDIF and LUCELG were intro-
duced in [2,3]. These are Diffie-Hellman and ElGamal
algorithms formulated with Lucas sequences


,
k
VPQ
where . Several method for efficient com-
putation of such sequences were subsequently published
in [4,5] and [6]. The computation of Lucas sequences
with any Q is also valuable. In [1] th e authors generalize
the algorithm published in [4] for any type of Lucas se-
quences. In this paper we propose a change for this algo-
rithm that significantly improves its average running
time.
1modQp
Such an algorithm could be useful for various pur-
poses. As an example the authors suggest using it to
compute the order of an elliptic curve. We can suggest
using it for cryptosystems based on exponentiation of
Gaussian integers (for example [7,8]). Gaussian integer
exponentiation can be expressed in terms of Lucas se-
quences and vise versa ([9]). In fact, efficient algorithm
to compute Lucas sequences could have many possible
applications that we can’ t anticipate at this time.
2. Overview of Lucas Sequences
Lucas sequences are defined as sequences


,
k
UPQ
and () by recurrence relations:

,
k
VPQ 24PQ0
2k
2k

01 1
0; 1;,
kk
UUUPQPUQU

  (1)

01 1
2;; ,
kk
VVPVPQPVQV

 (2)
Lucas sequences have many interesting properties and
relations ([10] can be used for a reference). For the pur-
poses of this paper we are interested in the following
relation:
1
2
2
4
k
k
VPV
UPQ


k
(3)
3. Algorithm to Compute Vk and Uk
Algorithm 3.1. Algorithm to compute Vk and Uk
Inputs: , where
1
0
2
ni
i
i
kk


2 lognk

(P, Q)–Lucas sequence parameters
Outputs: (Vk, Uk)
1) Vl := 2; Vh := P;
2) Ql := 1; Qh := 1 ;
3) for j = n – 1 downto 0
4) Q
l := Ql * Qh;
5) if (k[j] = 1)
6) Qh := Ql * Q;
7) Vl := Vh * Vl – P * Ql;
8) Vh := Vh * Vh – 2 * Qh;
9) else
10) Qh := Ql;
11) Vh := Vh * Vl – P * Ql;
12) Vl := Vl * Vl – 2 * Qh;
13) endif
14) endfor
15) Uk := (2 * Vh – P * Vl)/(P * P – 4 * Q);
16) return (Vl,Uk)
The Algorithm 3.1 looks very much like the algorithm
in [1]. The difference is that we do not compute Uh as it
is done in [1]. Instead we use relation (3) to compute Uk

944 A. KOVAL
on line 15. This allows us to significantly cut the nu mber
of multiplications. For a random k the number of multi-
plications in the algorithm presented in [1] is 2
11log
2
k.
The number of multiplications in the Algorithm 3.1 is
2
9log 2
2
k. (4)
Note: the multiplication by a small constants (2 or 4)
on lines 8, 12 and 14 have the running time of additions
and, therefore, are not included in Equ ation (4).
4. Conclusions
In this paper we presented an improved algorithm to
compute Lucas sequences Vk and Uk. The proposed algo-
rithm allows for approximately 20% improvement in
running time, which could be significant, especially if it
is used in real time cryptographic systems. Moreover, the
improved algorithm does not require any special precal-
culations and there are no tradeoffs or restrictions.
5. References
[1] M. Joye and J. J. Quisquater, “Efficient Computation of
Full Lucas Sequences,” Electronics Letters, Vol. 32, No.
6, 1996, pp. 537-538.
[2] P. Smith, “Cryptography without Exponentiation,” Dr.
Dobb’s Journal, Vol. 19, No. 4, April 1994, pp. 26-30.
[3] P. Smith, “Luc Public Key Encryption: A Secure Alterna-
tive to RSA,” Dr. Dobb’s Journal, Vol. 18, No. 1, 1993,
pp. 44-49.
[4] S. M. Yen and C. S. Laih, “Fast Algorithms for Luc
Digital Signature Computation,” IEE Proceedings: Com-
puters and Digital Techniques, Vol. 142, No. 2, 1995, pp.
165-169.
[5] C.-T. Wang, C.-C. Chang and C.-H. Lin, “A Method for
Computing Lucas Sequences,” Computers & Mathemat-
ics with Applications, Vol. 38, No. 11-12, 1999, pp. 187-
196.
[6] M. Othman, E. M. Abulhirat, Z. M. Ali, M. R. M. Said
and R. Johari, “A New Computation Algorithm for a
Cryptosystem Based on Lucas Functions,” Journal of
Computer Science, Vol. 4, No. 12, 2008, pp. 1056-1060.
[7] A. El-Kassar, M. Rizk, N. Mirza and Y. Awad, “El-Ga-
mal Public-Key Cryptosystem in the Domain of Gaussian
Integers,” International Journal of Applied Mathematics,
Vol. 7, No. 4, 2001, pp. 405-412.
[8] H. Elkamchouchi, K. Elshenawy and H. Shaban, “Ex-
tended RSA Cryptosystem and Digital Signature Schemes
in the Domain of Gaussian Integers,” Proceedings of the
8th IEEE International Conference on Communication
Systems, Singapore, Vol. 1, 25-28 November 2002, pp.
91-95.
[9] A. Koval and B. S. Verkhovsky, “On Discrete Logarithm
Problem for Gaussian Integers,” Proceedings of Interna-
tional Conference on Information Security and Privacy,
Orlando, 13-16 July 2009, pp. 79-84.
[10] L. E. Dickson, “Recurring Series; Lucas’ Un, Vn,” History
of the Theory of Numbers: Divisibility and Primality,
Dover Publications, New York, Vol. 1, 2005, pp. 393-
411.